SCIP
Solving Constraint Integer Programs
heur_indicatordiving.c File Reference
Detailed Description
LP diving heuristic that fixes indicator variables controlling semicontinuous variables.
A diving heuristic iteratively rounds some fractional variables or variables determined by constraint handlers, and resolves the LP relaxation. Thereby simulating a depth-first-search in the tree.
Indicatordiving focuses on indicator variables, which control semicontinuous variables. If the semicontinuous variable is unbounded, the indicator constraint is not part of the LP and, therefore, the indicator variable is not set to an useful value in the LP solution.
For these indicator variables the score depends on the LP value and the bounds of the corresponding semicontinuous variable. If parameter usevarbounds=TRUE, also varbound constraints modeling semicontinuous variables are considered. For all other variables the Farkas score (scaled) is returned.
Definition in file heur_indicatordiving.c.
#include <assert.h>#include "scip/cons_indicator.h"#include "scip/cons_varbound.h"#include "scip/heur_indicatordiving.h"#include "scip/heuristics.h"#include "scip/pub_cons.h"#include "scip/pub_heur.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_var.h"#include "scip/scip_cons.h"#include "scip/scip_heur.h"#include "scip/scip_mem.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_probing.h"#include "scip/scip_sol.h"#include "scip/scip_tree.h"#include "scip/scip_prob.h"#include "scip/scip_message.h"Go to the source code of this file.
Data Structures | |
| struct | SCVarData |
Typedefs | |
| typedef enum IndicatorDivingRoundingMode | INDICATORDIVINGROUNDINGMODE |
| typedef struct SCVarData | SCVARDATA |
Enumerations | |
| enum | IndicatorDivingRoundingMode { ROUNDING_CONSERVATIVE = 0 , ROUNDING_AGGRESSIVE = 1 } |
Functions | |
| static SCIP_Bool | isViolatedAndNotFixed (SCIP *scip, SCIP_SOL *sol, SCIP_CONS *cons) |
| static SCIP_RETCODE | releaseSCHashmap (SCIP *scip, SCIP_HASHMAP *hashmap) |
| static void | checkAndGetIndicator (SCIP *scip, SCIP_VAR *cand, SCIP_HASHMAP *map, SCIP_CONS **cons, SCIP_Bool *isindicator, SCIP_Bool *containsviolindconss, SCIP_Bool newnode, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr) |
| static void | checkAndGetVarbound (SCIP *scip, SCIP_VAR *cand, SCIP_HASHMAP *map, SCIP_CONS **cons, SCIP_Bool *isvarbound) |
| static SCIP_RETCODE | addSCVarIndicator (SCIP *scip, SCVARDATA *scvdata, SCIP_VAR *indicator, SCIP_Real val0, SCIP_Real lb1, SCIP_Real ub1) |
| static SCIP_RETCODE | varIsSemicontinuous (SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *scvars, SCIP_Real constant, SCIP_Bool *result) |
| static SCIP_RETCODE | hasUnfixedSCIndicator (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HASHMAP *scvars, SCIP_Bool *hasunfixedscindconss) |
| static SCIP_RETCODE | createMaps (SCIP *scip, SCIP_CONSHDLR *indicatorconshdlr, SCIP_CONSHDLR *varboundconshdlr, SCIP_Bool usevarbounds, SCIP_HASHMAP **indicatormap, SCIP_HASHMAP **varboundmap) |
| static void | getScoreOfFarkasDiving (SCIP *scip, SCIP_DIVESET *diveset, SCIP_VAR *cand, SCIP_Real candsfrac, SCIP_Bool *roundup, SCIP_Real *score) |
| static | SCIP_DECL_HEURCOPY (heurCopyIndicatordiving) |
| static | SCIP_DECL_HEURFREE (heurFreeIndicatordiving) |
| static | SCIP_DECL_HEURINIT (heurInitIndicatordiving) |
| static | SCIP_DECL_HEUREXIT (heurExitIndicatordiving) |
| static | SCIP_DECL_HEUREXEC (heurExecIndicatordiving) |
| static | SCIP_DECL_DIVESETGETSCORE (divesetGetScoreIndicatordiving) |
| static | SCIP_DECL_DIVESETAVAILABLE (divesetAvailableIndicatordiving) |
| SCIP_RETCODE | SCIPincludeHeurIndicatordiving (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
| #define HEUR_NAME "indicatordiving" |
Definition at line 67 of file heur_indicatordiving.c.
◆ HEUR_DESC
| #define HEUR_DESC "LP diving heuristic that fixes indicator variables controlling semicontinuous variables" |
Definition at line 68 of file heur_indicatordiving.c.
◆ HEUR_DISPCHAR
| #define HEUR_DISPCHAR 'I' |
Definition at line 69 of file heur_indicatordiving.c.
◆ HEUR_PRIORITY
| #define HEUR_PRIORITY -150000 |
Definition at line 70 of file heur_indicatordiving.c.
◆ HEUR_FREQ
| #define HEUR_FREQ 0 |
Definition at line 71 of file heur_indicatordiving.c.
◆ HEUR_FREQOFS
| #define HEUR_FREQOFS 0 |
Definition at line 72 of file heur_indicatordiving.c.
◆ HEUR_MAXDEPTH
| #define HEUR_MAXDEPTH -1 |
Definition at line 73 of file heur_indicatordiving.c.
◆ HEUR_TIMING
| #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
Definition at line 74 of file heur_indicatordiving.c.
◆ HEUR_USESSUBSCIP
| #define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 75 of file heur_indicatordiving.c.
◆ DIVESET_DIVETYPES
| #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY |
bit mask that represents all supported dive types
Definition at line 76 of file heur_indicatordiving.c.
◆ DIVESET_ISPUBLIC
| #define DIVESET_ISPUBLIC FALSE |
is this dive set publicly available (ie., can be used by other primal heuristics?)
Definition at line 77 of file heur_indicatordiving.c.
◆ DEFAULT_MINRELDEPTH
| #define DEFAULT_MINRELDEPTH 0.0 |
minimal relative depth to start diving
Definition at line 84 of file heur_indicatordiving.c.
◆ DEFAULT_MAXRELDEPTH
| #define DEFAULT_MAXRELDEPTH 1.0 |
maximal relative depth to start diving
Definition at line 85 of file heur_indicatordiving.c.
◆ DEFAULT_MAXLPITERQUOT
| #define DEFAULT_MAXLPITERQUOT 0.05 |
maximal fraction of diving LP iterations compared to node LP iterations
Definition at line 86 of file heur_indicatordiving.c.
◆ DEFAULT_MAXLPITEROFS
| #define DEFAULT_MAXLPITEROFS 1000 |
additional number of allowed LP iterations
Definition at line 87 of file heur_indicatordiving.c.
◆ DEFAULT_MAXDIVEUBQUOT
| #define DEFAULT_MAXDIVEUBQUOT 0.8 |
maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)
Definition at line 89 of file heur_indicatordiving.c.
◆ DEFAULT_MAXDIVEAVGQUOT
| #define DEFAULT_MAXDIVEAVGQUOT 0.0 |
maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)
Definition at line 91 of file heur_indicatordiving.c.
◆ DEFAULT_MAXDIVEUBQUOTNOSOL
| #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 |
maximal UBQUOT when no solution was found yet (0.0: no limit)
Definition at line 92 of file heur_indicatordiving.c.
◆ DEFAULT_MAXDIVEAVGQUOTNOSOL
| #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 |
maximal AVGQUOT when no solution was found yet (0.0: no limit)
Definition at line 93 of file heur_indicatordiving.c.
◆ DEFAULT_BACKTRACK
| #define DEFAULT_BACKTRACK TRUE |
use one level of backtracking if infeasibility is encountered?
Definition at line 94 of file heur_indicatordiving.c.
◆ DEFAULT_LPRESOLVEDOMCHGQUOT
| #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 |
percentage of immediate domain changes during probing to trigger LP resolve
Definition at line 95 of file heur_indicatordiving.c.
◆ DEFAULT_LPSOLVEFREQ
| #define DEFAULT_LPSOLVEFREQ 30 |
LP solve frequency for diving heuristics
Definition at line 96 of file heur_indicatordiving.c.
◆ DEFAULT_ONLYLPBRANCHCANDS
| #define DEFAULT_ONLYLPBRANCHCANDS FALSE |
should only LP branching candidates be considered instead of the slower but more general constraint handler diving variable selection?
Definition at line 98 of file heur_indicatordiving.c.
◆ DEFAULT_RANDSEED
| #define DEFAULT_RANDSEED 11 |
initial seed for random number generation
Definition at line 99 of file heur_indicatordiving.c.
◆ DEFAULT_ROUNDINGFRAC
| #define DEFAULT_ROUNDINGFRAC 0.5 |
default setting for parameter roundingfrac
Definition at line 104 of file heur_indicatordiving.c.
◆ DEFAULT_ROUNDINGMODE
| #define DEFAULT_ROUNDINGMODE 0 |
default setting for parameter roundingmode
Definition at line 105 of file heur_indicatordiving.c.
◆ DEFAULT_SEMICONTSCOREMODE
| #define DEFAULT_SEMICONTSCOREMODE 0 |
default setting for parameter semicontscoremode
Definition at line 106 of file heur_indicatordiving.c.
◆ DEFAULT_USEVARBOUNDS
| #define DEFAULT_USEVARBOUNDS TRUE |
default setting for parameter usevarbounds
Definition at line 107 of file heur_indicatordiving.c.
◆ DEFAULT_RUNWITHOUTSCINDS
| #define DEFAULT_RUNWITHOUTSCINDS FALSE |
default setting for parameter runwithoutscinds
Definition at line 108 of file heur_indicatordiving.c.
◆ MIN_RAND
| #define MIN_RAND 1e-06 |
Definition at line 639 of file heur_indicatordiving.c.
◆ MAX_RAND
| #define MAX_RAND 1e-05 |
Definition at line 640 of file heur_indicatordiving.c.
Typedef Documentation
◆ INDICATORDIVINGROUNDINGMODE
| typedef enum IndicatorDivingRoundingMode INDICATORDIVINGROUNDINGMODE |
Definition at line 115 of file heur_indicatordiving.c.
◆ SCVARDATA
Definition at line 133 of file heur_indicatordiving.c.
Enumeration Type Documentation
◆ IndicatorDivingRoundingMode
| Enumerator | |
|---|---|
| ROUNDING_CONSERVATIVE | |
| ROUNDING_AGGRESSIVE | |
Definition at line 110 of file heur_indicatordiving.c.
Function Documentation
◆ isViolatedAndNotFixed()
checks if constraint is violated but not fixed, i.e., it will be a diving candidate variable
- Parameters
-
scip SCIP data structure sol pointer to solution cons pointer to indicator constraint
Definition at line 162 of file heur_indicatordiving.c.
References FALSE, SCIP_Real, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPgetBinaryVarIndicator(), SCIPgetSolVal(), SCIPisFeasIntegral(), SCIPisViolatedIndicator(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by checkAndGetIndicator().
◆ releaseSCHashmap()
|
static |
releases all data from given hashmap filled with SCVarData and the hashmap itself
- Parameters
-
scip SCIP data structure hashmap hashmap to be freed
Definition at line 184 of file heur_indicatordiving.c.
References SCVarData::bndssize, SCVarData::bvars, SCVarData::lbs1, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPhashmapEntryGetImage(), SCIPhashmapFree(), SCIPhashmapGetEntry(), SCIPhashmapGetNEntries(), SCVarData::ubs1, and SCVarData::vals0.
Referenced by SCIP_DECL_HEUREXIT().
◆ checkAndGetIndicator()
|
static |
checks if variable is indicator variable and stores corresponding indicator constraint; additionally, if we are at a new probing node, it checks whether there are violated but not fixed indicator constraints
- Parameters
-
scip SCIP data structure cand candidate variable map pointer to hashmap containing indicator conss cons pointer to store indicator constraint isindicator pointer to store whether candidate variable is indicator variable containsviolindconss pointer to store whether there are violated and not fixed (unbounded) indicator constraints newnode are we at a new probing node? sol pointer to solution conshdlr constraint handler
Definition at line 219 of file heur_indicatordiving.c.
References FALSE, isViolatedAndNotFixed(), NULL, SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPhashmapGetImage(), and TRUE.
Referenced by SCIP_DECL_DIVESETGETSCORE().
◆ checkAndGetVarbound()
|
static |
checks if variable is binary variable of varbound constraint and stores corresponding varbound constraint
- Parameters
-
scip SCIP data structure cand candidate variable map pointer to hashmap containing varbound conss cons pointer to store varbound constraint isvarbound pointer to store whether candidate variable is indicator variable
Definition at line 268 of file heur_indicatordiving.c.
References FALSE, NULL, SCIP_VARTYPE_BINARY, SCIPhashmapGetImage(), SCIPvarGetType(), and TRUE.
Referenced by SCIP_DECL_DIVESETGETSCORE().
◆ addSCVarIndicator()
|
static |
adds an indicator to the data of a semicontinuous variable
- Parameters
-
scip SCIP data structure scvdata semicontinuous variable data indicator indicator to be added val0 value of the variable when indicator == 0 lb1 lower bound of the variable when indicator == 1 ub1 upper bound of the variable when indicator == 1
Definition at line 295 of file heur_indicatordiving.c.
References SCVarData::bndssize, SCVarData::bvars, FALSE, SCVarData::lbs1, SCVarData::nbnds, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPreallocBlockMemoryArray, SCIPsortedvecFindPtr(), SCVarData::ubs1, and SCVarData::vals0.
Referenced by varIsSemicontinuous().
◆ varIsSemicontinuous()
|
static |
checks if a variable is semicontinuous and stores it data in the hashmap scvars
A variable x is semicontinuous if its bounds depend on at least one binary variable called the indicator, and indicator == 0 => x == x^0 for some real constant x^0.
- Parameters
-
scip SCIP data structure var the variable to check scvars semicontinuous variable information constant value which should be equal to the constant result buffer to store whether var is semicontinuous
Definition at line 365 of file heur_indicatordiving.c.
References addSCVarIndicator(), SCVarData::bvars, FALSE, MAX, MIN, SCVarData::nbnds, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocClearBlockMemory, SCIPdebugMsg, SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPisEQ(), SCIPsortedvecFindPtr(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), TRUE, and SCVarData::vals0.
Referenced by hasUnfixedSCIndicator(), and SCIP_DECL_DIVESETGETSCORE().
◆ hasUnfixedSCIndicator()
|
static |
checks if there are unfixed indicator variables modeling semicont. vars
- Parameters
-
scip SCIP data structure conshdlr indicator constraint handler scvars semicontinuous variable information hasunfixedscindconss pointer to store if there are unfixed indicator variables modeling semicont. vars
Definition at line 514 of file heur_indicatordiving.c.
References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetRhs(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfreeBufferArray, SCIPgetBinaryVarIndicator(), SCIPgetConsNVars(), SCIPgetConsVals(), SCIPgetConsVars(), SCIPgetLinearConsIndicator(), SCIPgetSlackVarIndicator(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and varIsSemicontinuous().
Referenced by SCIP_DECL_HEUREXEC().
◆ createMaps()
|
static |
creates and initializes hashmaps
indicatormap: binary var -> indicator constraint varboundmap: binary var -> varbound constraint
Currently exactly one constraint is assigned to a binary variable (per hashmap), but a binary variable can also control more than one constraint. TODO: Allow more than one corresponding indicator/varbound constraint per binary variable.
- Parameters
-
scip SCIP data structure indicatorconshdlr indicator constraint handler varboundconshdlr varbound constraint handler usevarbounds should varbound constraints be considered? indicatormap hashmap to store indicator constraints of binary variables varboundmap hashmap to store varbound constraints of binary variables
Definition at line 594 of file heur_indicatordiving.c.
References SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPconshdlrGetConss(), SCIPconshdlrGetName(), SCIPconshdlrGetNConss(), SCIPgetBinaryVarIndicator(), SCIPgetVbdvarVarbound(), SCIPhashmapCreate(), SCIPhashmapExists(), and SCIPhashmapInsert().
Referenced by SCIP_DECL_HEUREXEC().
◆ getScoreOfFarkasDiving()
|
static |
calculate score and preferred rounding direction for the candidate variable
- Parameters
-
scip SCIP data structure diveset diving settings cand candidate variable candsfrac fractional part of solution value of candidate variable roundup pointer to store whether the preferred rounding direction is upwards score pointer for diving score value
Definition at line 644 of file heur_indicatordiving.c.
References FALSE, MAX_RAND, MIN_RAND, NULL, REALABS, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPdivesetGetRandnumgen(), SCIPisEQ(), SCIPisNegative(), SCIPisPositive(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPvarGetObj(), SCIPvarGetType(), and TRUE.
Referenced by SCIP_DECL_DIVESETGETSCORE().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 691 of file heur_indicatordiving.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurIndicatordiving().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 706 of file heur_indicatordiving.c.
References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 727 of file heur_indicatordiving.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPcreateSol(), SCIPfindConshdlr(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPheurGetData(), and SCIPheurGetName().
◆ SCIP_DECL_HEUREXIT()
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 752 of file heur_indicatordiving.c.
References HEUR_NAME, NULL, releaseSCHashmap(), SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), SCIPheurGetData(), and SCIPheurGetName().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 774 of file heur_indicatordiving.c.
References createMaps(), FALSE, hasUnfixedSCIndicator(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_DIVECONTEXT_SINGLE, SCIP_OKAY, SCIPconshdlrGetNConss(), SCIPdebugMsg, SCIPgetDepth(), SCIPhashmapFree(), SCIPheurGetData(), SCIPheurGetDivesets(), SCIPheurGetNDivesets(), SCIPperformGenericDivingAlgorithm(), SCIP_Diveset::sol, and TRUE.
◆ SCIP_DECL_DIVESETGETSCORE()
|
static |
calculate score and preferred rounding direction for the candidate variable
Definition at line 826 of file heur_indicatordiving.c.
References b, SCVarData::bvars, checkAndGetIndicator(), checkAndGetVarbound(), FALSE, getScoreOfFarkasDiving(), SCVarData::lbs1, SCVarData::nbnds, NULL, ROUNDING_AGGRESSIVE, ROUNDING_CONSERVATIVE, SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPallocBufferArray, SCIPconsGetLhs(), SCIPconsGetRhs(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdivesetGetHeur(), SCIPdivesetGetRandnumgen(), SCIPfreeBufferArray, SCIPgetConsNVars(), SCIPgetConsVals(), SCIPgetConsVars(), SCIPgetLinearConsIndicator(), SCIPgetProbingDepth(), SCIPgetSlackVarIndicator(), SCIPgetVbdvarVarbound(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPisEQ(), SCIPisFeasIntegral(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisZero(), SCIPrandomGetReal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetNegationVar(), SCIPvarGetObj(), SCIPvarGetUbLocal(), SCIPvarIsNegated(), TRUE, SCVarData::ubs1, SCVarData::vals0, and varIsSemicontinuous().
◆ SCIP_DECL_DIVESETAVAILABLE()
|
static |
callback to check preconditions for diving, e.g., if an incumbent solution is available
Definition at line 1097 of file heur_indicatordiving.c.
References NULL, SCIP_OKAY, SCIPconshdlrGetNActiveConss(), SCIPdivesetGetHeur(), SCIPfindConshdlr(), and SCIPheurGetData().