Scippy

SCIP

Solving Constraint Integer Programs

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"
#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
varsvariable array
valsvalue array
nvarsnumber of variables
signature0pointer to store the signatures of variables fixed to 0
signature1pointer 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
scipSCIP data structure
comprcompression method
comprdatacompression data
resultresult 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
scipSCIP data structure
comprcompression method
comprdatacompression data
resultresult 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
SCIP_RETCODE SCIPincludeComprLargestrepr ( SCIP scip)

creates the largestrepr tree compression and includes it in SCIP

Parameters
scipSCIP 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().