Scippy

    SCIP

    Solving Constraint Integer Programs

    Macros | Functions
    compr_largestrepr.c File Reference
    Implementation files (.c files) » SCIP Default Plugins » Default tree compressions

    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"

    Definition at line 50 of file compr_largestrepr.c.

    ◆ COMPR_DESC

    #define COMPR_DESC   "heuristic searching for large common representatives"

    Definition at line 51 of file compr_largestrepr.c.

    ◆ COMPR_PRIORITY

    #define COMPR_PRIORITY   2000

    Definition at line 52 of file compr_largestrepr.c.

    ◆ COMPR_MINNNODES

    #define COMPR_MINNNODES   20

    Definition at line 53 of file compr_largestrepr.c.

    ◆ DEFAUL_MEM_REPR

    #define DEFAUL_MEM_REPR   10

    Definition at line 55 of file compr_largestrepr.c.

    ◆ DEFAULT_ITERS

    #define DEFAULT_ITERS   5

    Definition at line 56 of file compr_largestrepr.c.

    ◆ DEFAULT_MINCOMMONVARS

    #define DEFAULT_MINCOMMONVARS   3

    Definition at line 57 of file compr_largestrepr.c.

    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 90 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 126 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 611 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 651 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 665 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 683 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 711 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
    scipSCIP data structure

    Definition at line 763 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().