compr_largestrepr.c File Reference

Detailed Description

largestrepr tree compression

Author

Jakob Witzig

Definition in file compr_largestrepr.c.

#include <assert.h>
#include <string.h>
#include "scip/compr_largestrepr.h"
#include "scip/compr.h"
#include "scip/pub_reopt.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, SCIP_Longint *signature0, SCIP_Longint *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

#define COMPR_NAME   "largestrepr"

Definition at line 31 of file compr_largestrepr.c.

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

#define COMPR_DESC   "heuristic searching for large common representatives"

Definition at line 32 of file compr_largestrepr.c.

Referenced by SCIPincludeComprLargestrepr().

#define COMPR_PRIORITY   2000

Definition at line 33 of file compr_largestrepr.c.

Referenced by SCIPincludeComprLargestrepr().

#define COMPR_MINNNODES   20

Definition at line 34 of file compr_largestrepr.c.

Referenced by SCIPincludeComprLargestrepr().

#define DEFAUL_MEM_REPR   10

Definition at line 36 of file compr_largestrepr.c.

Referenced by SCIP_DECL_COMPREXEC().

#define DEFAULT_ITERS   5

Definition at line 37 of file compr_largestrepr.c.

Referenced by SCIPincludeComprLargestrepr().

#define DEFAULT_MINCOMMONVARS   3

Definition at line 38 of file compr_largestrepr.c.

Referenced by SCIPincludeComprLargestrepr().

Function Documentation

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

static

calculate a signature of variables fixed to 0 and 1 by using binary shift and or operations. we calculate the signature on the basis of SCIPvarGetProbindex() % 64

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 72 of file compr_largestrepr.c.

References SCIPvarGetProbindex().

Referenced by 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 106 of file compr_largestrepr.c.

References calcSignature(), COMPR_NAME, FALSE, MAX, NULL, REOPT_CONSTYPE_STRBRANCHED, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVED, SCIP_SUCCESS, SCIPaddReoptnodeBndchg(), SCIPaddReoptnodeCons(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocClearMemoryArray, SCIPcomprGetMinNodes(), SCIPdebugMessage, SCIPfindVar(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPfreeRepresentation(), SCIPgetNBinVars(), SCIPgetNOrigVars(), SCIPgetNReoptLeaves(), SCIPgetReoptLeaveIDs(), SCIPgetReoptnode(), SCIPgetReoptnodePath(), SCIPgetStage(), SCIPinitRepresentation(), SCIPisFeasEQ(), SCIPreallocMemoryArray, SCIPreoptnodeGetNVars(), SCIPresetRepresentation(), SCIPvarGetName(), SCIPvarGetProbindex(), and TRUE.

Referenced by SCIP_DECL_COMPREXEC().

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 550 of file compr_largestrepr.c.

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

Referenced by SCIP_DECL_COMPREXEC().

static SCIP_DECL_COMPRCOPY ( comprCopyLargestrepr  )

static

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

Definition at line 590 of file compr_largestrepr.c.

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

static SCIP_DECL_COMPRFREE ( comprFreeLargestrepr  )

static

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

Definition at line 604 of file compr_largestrepr.c.

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

static SCIP_DECL_COMPREXIT ( comprExitLargestrepr  )

static

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

Definition at line 622 of file compr_largestrepr.c.

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

static SCIP_DECL_COMPREXEC ( comprExecLargestrepr  )

static

execution method of tree compression

Definition at line 650 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(), SCIPdebugMessage, SCIPfreeRepresentation(), SCIPinitRepresentation(), and TRUE.

SCIP_RETCODE SCIPincludeComprLargestrepr

(

SCIP *

scip

)

creates the largestrepr tree compression and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 702 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(), SCIPallocMemory, SCIPincludeComprBasic(), SCIPsetComprCopy(), SCIPsetComprExit(), and SCIPsetComprFree().

Referenced by SCIP_DECL_COMPRCOPY(), and SCIPincludeDefaultPlugins().