Detailed Description

largestrepr tree compression

Author: Jakob Witzig

#include "blockmemshell/memory.h"
#include "scip/compr_largestrepr.h"
#include "scip/pub_compr.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_reopt.h"
#include "scip/pub_var.h"
#include "scip/scip_compr.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_reopt.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	COMPR_NAME "largestrepr"

#define	COMPR_DESC "heuristic searching for large common representatives"

#define	COMPR_PRIORITY 2000

#define	COMPR_MINNNODES 20

#define	DEFAUL_MEM_REPR 10

#define	DEFAULT_ITERS 5

#define	DEFAULT_MINCOMMONVARS 3

Functions
static void	calcSignature (SCIP_VAR *vars, SCIP_Real vals, int nvars, uint64_t signature0, uint64_t signature1)

static SCIP_RETCODE	constructCompression (SCIP scip, SCIP_COMPR compr, SCIP_COMPRDATA comprdata, SCIP_RESULT result)

static SCIP_RETCODE	applyCompression (SCIP scip, SCIP_COMPR compr, SCIP_COMPRDATA comprdata, SCIP_RESULT result)

static	SCIP_DECL_COMPRCOPY (comprCopyLargestrepr)

static	SCIP_DECL_COMPRFREE (comprFreeLargestrepr)

static	SCIP_DECL_COMPREXIT (comprExitLargestrepr)

static	SCIP_DECL_COMPREXEC (comprExecLargestrepr)

SCIP_RETCODE	SCIPincludeComprLargestrepr (SCIP *scip)

Macro Definition Documentation

◆ COMPR_NAME

#define COMPR_NAME "largestrepr"

Definition at line 41 of file compr_largestrepr.c.

Referenced by constructCompression(), SCIP_DECL_COMPRCOPY(), SCIP_DECL_COMPREXEC(), and SCIPincludeComprLargestrepr().

◆ COMPR_DESC

#define COMPR_DESC "heuristic searching for large common representatives"

Definition at line 42 of file compr_largestrepr.c.

Referenced by SCIPincludeComprLargestrepr().

◆ COMPR_PRIORITY

#define COMPR_PRIORITY 2000

Definition at line 43 of file compr_largestrepr.c.

Referenced by SCIPincludeComprLargestrepr().

◆ COMPR_MINNNODES

#define COMPR_MINNNODES 20

Definition at line 44 of file compr_largestrepr.c.

Referenced by SCIPincludeComprLargestrepr().

◆ DEFAUL_MEM_REPR

#define DEFAUL_MEM_REPR 10

Definition at line 46 of file compr_largestrepr.c.

Referenced by SCIP_DECL_COMPREXEC().

◆ DEFAULT_ITERS

#define DEFAULT_ITERS 5

Definition at line 47 of file compr_largestrepr.c.

Referenced by SCIPincludeComprLargestrepr().

◆ DEFAULT_MINCOMMONVARS

#define DEFAULT_MINCOMMONVARS 3

Definition at line 48 of file compr_largestrepr.c.

Referenced by SCIPincludeComprLargestrepr().

Function Documentation

◆ calcSignature()

static void calcSignature	(	SCIP_VAR **	vars,
		SCIP_Real *	vals,
		int	nvars,
		uint64_t *	signature0,
		uint64_t *	signature1
	)

static

calculate a bit signature of variables fixed to 0 and 1 on the basis of SCIPvarGetProbindex()

Parameters

vars	variable array
vals	value array
nvars	number of variables
signature0	pointer to store the signatures of variables fixed to 0
signature1	pointer to store the signatures of variables fixed to 1

Definition at line 81 of file compr_largestrepr.c.

References SCIPhashSignature64, and SCIPvarGetProbindex().

Referenced by constructCompression().

◆ constructCompression()

static SCIP_RETCODE constructCompression	(	SCIP *	scip,
		SCIP_COMPR *	compr,
		SCIP_COMPRDATA *	comprdata,
		SCIP_RESULT *	result
	)

static

try to find a representation of the current search frontier.

We use the signatures of variables fixed to 0 and 1 to decide if there is definitely no intersection or if the intersection is potentially non-empty.

To find a good representation we start the procedure with a node and choose the best one. the heuristic tries to find a representation of size 2 in each iteration, i.e., runs in the constrained part.

Parameters

scip	SCIP data structure
compr	compression method
comprdata	compression data
result	result pointer

Definition at line 117 of file compr_largestrepr.c.

References calcSignature(), COMPR_NAME, FALSE, MAX, NULL, r, REOPT_CONSTYPE_DUALREDS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVED, SCIP_SUCCESS, SCIPaddReoptnodeBndchg(), SCIPaddReoptnodeCons(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocClearBlockMemoryArray, SCIPallocClearBufferArray, SCIPcomprGetMinNodes(), SCIPdebugMessage, SCIPdebugMsg, SCIPfindVar(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPfreeRepresentation(), SCIPgetNBinVars(), SCIPgetNOrigVars(), SCIPgetNReoptLeaves(), SCIPgetReoptLeaveIDs(), SCIPgetReoptnode(), SCIPgetReoptnodePath(), SCIPgetStage(), SCIPinfinity(), SCIPinitRepresentation(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisSumGT(), SCIPreallocMemoryArray, SCIPreoptnodeGetLowerbound(), SCIPreoptnodeGetNVars(), SCIPresetRepresentation(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarIsOriginal(), and TRUE.

Referenced by SCIP_DECL_COMPREXEC().

◆ applyCompression()

static SCIP_RETCODE applyCompression	(	SCIP *	scip,
		SCIP_COMPR *	compr,
		SCIP_COMPRDATA *	comprdata,
		SCIP_RESULT *	result
	)

static

apply the found representation to the reopttree.

Parameters

scip	SCIP data structure
compr	compression method
comprdata	compression data
result	result pointer

Definition at line 602 of file compr_largestrepr.c.

References FALSE, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPfreeRepresentation(), SCIPreoptnodeSetParentID(), and SCIPsetReoptCompression().

Referenced by SCIP_DECL_COMPREXEC().

◆ SCIP_DECL_COMPRCOPY()

static SCIP_DECL_COMPRCOPY ( comprCopyLargestrepr )

static

copy method for tree compression plugins (called when SCIP copies plugins)

Definition at line 642 of file compr_largestrepr.c.

References COMPR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPcomprGetName(), and SCIPincludeComprLargestrepr().

◆ SCIP_DECL_COMPRFREE()

static SCIP_DECL_COMPRFREE ( comprFreeLargestrepr )

static

destructor of tree compression to free user data (called when SCIP is exiting)

Definition at line 656 of file compr_largestrepr.c.

References NULL, SCIP_OKAY, SCIPcomprGetData(), SCIPcomprSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_COMPREXIT()

static SCIP_DECL_COMPREXIT ( comprExitLargestrepr )

static

deinitialization method of tree compression (called before transformed problem is freed)

Definition at line 674 of file compr_largestrepr.c.

References FALSE, NULL, SCIP_OKAY, SCIPcomprGetData(), and SCIPfreeMemoryArray.

◆ SCIP_DECL_COMPREXEC()

static SCIP_DECL_COMPREXEC ( comprExecLargestrepr )

static

execution method of tree compression

Definition at line 702 of file compr_largestrepr.c.

References applyCompression(), COMPR_NAME, constructCompression(), DEFAUL_MEM_REPR, NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPallocClearMemoryArray, SCIPcomprGetData(), SCIPdebugMsg, SCIPfreeRepresentation(), SCIPinitRepresentation(), and TRUE.

◆ SCIPincludeComprLargestrepr()

SCIP_RETCODE SCIPincludeComprLargestrepr ( SCIP * scip )

creates the largestrepr tree compression and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 754 of file compr_largestrepr.c.

References COMPR_DESC, COMPR_MINNNODES, COMPR_NAME, COMPR_PRIORITY, DEFAULT_ITERS, DEFAULT_MINCOMMONVARS, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddIntParam(), SCIPallocBlockMemory, SCIPincludeComprBasic(), SCIPsetComprCopy(), SCIPsetComprExit(), and SCIPsetComprFree().

Referenced by SCIP_DECL_COMPRCOPY(), and SCIPincludeDefaultPlugins().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ COMPR_NAME

◆ COMPR_DESC

◆ COMPR_PRIORITY

◆ COMPR_MINNNODES

◆ DEFAUL_MEM_REPR

◆ DEFAULT_ITERS

◆ DEFAULT_MINCOMMONVARS

Function Documentation

◆ calcSignature()

◆ constructCompression()

◆ applyCompression()

◆ SCIP_DECL_COMPRCOPY()

◆ SCIP_DECL_COMPRFREE()

◆ SCIP_DECL_COMPREXIT()

◆ SCIP_DECL_COMPREXEC()

◆ SCIPincludeComprLargestrepr()