Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

largestrepr tree compression

Author
Jakob Witzig

Definition in file compr_largestrepr.c.

#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"

◆ 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
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 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
scipSCIP data structure
comprcompression method
comprdatacompression data
resultresult 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
scipSCIP data structure
comprcompression method
comprdatacompression data
resultresult 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

◆ SCIPincludeComprLargestrepr()

SCIP_RETCODE SCIPincludeComprLargestrepr ( SCIP scip)

creates the largestrepr tree compression and includes it in SCIP

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