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 |
#define HEUR_NAME "indicatordiving" |
Definition at line 67 of file heur_indicatordiving.c.
#define HEUR_DESC "LP diving heuristic that fixes indicator variables controlling semicontinuous variables" |
Definition at line 68 of file heur_indicatordiving.c.
#define HEUR_DISPCHAR 'I' |
Definition at line 69 of file heur_indicatordiving.c.
#define HEUR_PRIORITY -150000 |
Definition at line 70 of file heur_indicatordiving.c.
#define HEUR_FREQ 0 |
Definition at line 71 of file heur_indicatordiving.c.
#define HEUR_FREQOFS 0 |
Definition at line 72 of file heur_indicatordiving.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 73 of file heur_indicatordiving.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
Definition at line 74 of file heur_indicatordiving.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 75 of file heur_indicatordiving.c.
#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY |
bit mask that represents all supported dive types
Definition at line 76 of file heur_indicatordiving.c.
#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.
#define DEFAULT_MINRELDEPTH 0.0 |
minimal relative depth to start diving
Definition at line 84 of file heur_indicatordiving.c.
#define DEFAULT_MAXRELDEPTH 1.0 |
maximal relative depth to start diving
Definition at line 85 of file heur_indicatordiving.c.
#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.
#define DEFAULT_MAXLPITEROFS 1000 |
additional number of allowed LP iterations
Definition at line 87 of file heur_indicatordiving.c.
#define DEFAULT_MAXDIVEUBQUOT 0.8 |
maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)
Definition at line 88 of file heur_indicatordiving.c.
#define DEFAULT_MAXDIVEAVGQUOT 0.0 |
maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)
Definition at line 90 of file heur_indicatordiving.c.
#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.
#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.
#define DEFAULT_BACKTRACK TRUE |
use one level of backtracking if infeasibility is encountered?
Definition at line 94 of file heur_indicatordiving.c.
#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.
#define DEFAULT_LPSOLVEFREQ 30 |
LP solve frequency for diving heuristics
Definition at line 96 of file heur_indicatordiving.c.
#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 97 of file heur_indicatordiving.c.
#define DEFAULT_RANDSEED 11 |
initial seed for random number generation
Definition at line 99 of file heur_indicatordiving.c.
#define DEFAULT_ROUNDINGFRAC 0.5 |
default setting for parameter roundingfrac
Definition at line 104 of file heur_indicatordiving.c.
Referenced by SCIPincludeHeurIndicatordiving().
#define DEFAULT_ROUNDINGMODE 0 |
default setting for parameter roundingmode
Definition at line 105 of file heur_indicatordiving.c.
Referenced by SCIPincludeHeurIndicatordiving().
#define DEFAULT_SEMICONTSCOREMODE 0 |
default setting for parameter semicontscoremode
Definition at line 106 of file heur_indicatordiving.c.
Referenced by SCIPincludeHeurIndicatordiving().
#define DEFAULT_USEVARBOUNDS TRUE |
default setting for parameter usevarbounds
Definition at line 107 of file heur_indicatordiving.c.
Referenced by SCIPincludeHeurIndicatordiving().
#define DEFAULT_RUNWITHOUTSCINDS FALSE |
default setting for parameter runwithoutscinds
Definition at line 108 of file heur_indicatordiving.c.
Referenced by SCIPincludeHeurIndicatordiving().
#define MIN_RAND 1e-06 |
Definition at line 639 of file heur_indicatordiving.c.
#define MAX_RAND 1e-05 |
Definition at line 640 of file heur_indicatordiving.c.
typedef enum IndicatorDivingRoundingMode INDICATORDIVINGROUNDINGMODE |
Definition at line 115 of file heur_indicatordiving.c.
Definition at line 133 of file heur_indicatordiving.c.
Enumerator | |
---|---|
ROUNDING_CONSERVATIVE | |
ROUNDING_AGGRESSIVE |
Definition at line 110 of file heur_indicatordiving.c.
checks if constraint is violated but not fixed, i.e., it will be a diving candidate variable
scip | SCIP data structure |
sol | pointer to solution |
cons | pointer to indicator constraint |
Definition at line 162 of file heur_indicatordiving.c.
References assert(), FALSE, SCIP_Bool, SCIP_Real, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPgetBinaryVarIndicator(), SCIPgetSolVal(), SCIPisFeasIntegral(), SCIPisViolatedIndicator(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and sol.
Referenced by checkAndGetIndicator().
|
static |
releases all data from given hashmap filled with SCVarData and the hashmap itself
scip | SCIP data structure |
hashmap | hashmap to be freed |
Definition at line 184 of file heur_indicatordiving.c.
References assert(), SCVarData::bndssize, SCVarData::bvars, c, SCVarData::lbs1, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPhashmapEntryGetImage(), SCIPhashmapFree(), SCIPhashmapGetEntry(), SCIPhashmapGetNEntries(), SCVarData::ubs1, and SCVarData::vals0.
Referenced by SCIP_DECL_HEUREXIT().
|
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
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 assert(), c, FALSE, isViolatedAndNotFixed(), NULL, SCIP_Bool, SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPhashmapGetImage(), sol, and TRUE.
Referenced by SCIP_DECL_DIVESETGETSCORE().
|
static |
checks if variable is binary variable of varbound constraint and stores corresponding varbound constraint
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 assert(), FALSE, NULL, SCIP_Bool, SCIP_VARTYPE_BINARY, SCIPhashmapGetImage(), SCIPvarGetType(), and TRUE.
Referenced by SCIP_DECL_DIVESETGETSCORE().
|
static |
adds an indicator to the data of a semicontinuous variable
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 assert(), SCVarData::bndssize, SCVarData::bvars, FALSE, i, SCVarData::lbs1, SCVarData::nbnds, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcalcMemGrowSize(), SCIPreallocBlockMemoryArray, SCIPsortedvecFindPtr(), SCVarData::ubs1, and SCVarData::vals0.
Referenced by 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.
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(), assert(), SCVarData::bvars, c, FALSE, MAX, MIN, SCVarData::nbnds, NULL, result, 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, SCVarData::vals0, and var.
Referenced by hasUnfixedSCIndicator(), and SCIP_DECL_DIVESETGETSCORE().
|
static |
checks if there are unfixed indicator variables modeling semicont. vars
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, i, 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().
|
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.
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 assert(), i, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPconshdlrGetConss(), SCIPconshdlrGetName(), SCIPconshdlrGetNConss(), SCIPgetBinaryVarIndicator(), SCIPgetVbdvarVarbound(), SCIPhashmapCreate(), SCIPhashmapExists(), and SCIPhashmapInsert().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
calculate score and preferred rounding direction for the candidate variable
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 assert(), diveset, FALSE, MAX_RAND, MIN_RAND, NULL, obj, REALABS, roundup, SCIP_Bool, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPdivesetGetRandnumgen(), SCIPisEQ(), SCIPisNegative(), SCIPisPositive(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPvarGetObj(), SCIPvarGetType(), and TRUE.
Referenced by SCIP_DECL_DIVESETGETSCORE().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 691 of file heur_indicatordiving.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurIndicatordiving().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 706 of file heur_indicatordiving.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 727 of file heur_indicatordiving.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPcreateSol(), SCIPfindConshdlr(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPheurGetData(), and SCIPheurGetName().
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 752 of file heur_indicatordiving.c.
References assert(), HEUR_NAME, heurdata, NULL, releaseSCHashmap(), SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), SCIPheurGetData(), and SCIPheurGetName().
|
static |
execution method of primal heuristic
Definition at line 774 of file heur_indicatordiving.c.
References assert(), createMaps(), diveset, FALSE, hasUnfixedSCIndicator(), heurdata, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_DIVECONTEXT_SINGLE, SCIP_OKAY, SCIPconshdlrGetNConss(), SCIPdebugMsg, SCIPgetDepth(), SCIPhashmapFree(), SCIPheurGetData(), SCIPheurGetDivesets(), SCIPheurGetNDivesets(), SCIPperformGenericDivingAlgorithm(), and TRUE.
|
static |
calculate score and preferred rounding direction for the candidate variable
Definition at line 826 of file heur_indicatordiving.c.
References assert(), b, SCVarData::bvars, checkAndGetIndicator(), checkAndGetVarbound(), diveset, FALSE, getScoreOfFarkasDiving(), heurdata, SCVarData::lbs1, SCVarData::nbnds, NULL, ROUNDING_AGGRESSIVE, ROUNDING_CONSERVATIVE, roundup, 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().
|
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 assert(), diveset, heurdata, NULL, SCIP_OKAY, SCIPconshdlrGetNActiveConss(), SCIPdivesetGetHeur(), SCIPfindConshdlr(), and SCIPheurGetData().