LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood.
More details about the heuristic can be found in
Structure-Based Primal Heuristics for Mixed Integer Programming
Gerald Gamrath, Timo Berthold, Stefan Heinz, and Michael Winkler
Optimization in the Real World, Volume 13 of the series Mathematics for Industry, pp 37-53
Preliminary version available as ZIB-Report 15-26.
Definition in file heur_vbounds.c.
#include <assert.h>
#include <string.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/heur_vbounds.h"
#include "scip/heur_locks.h"
Go to the source code of this file.
Heuristic defines | |
The heuristic works on indices representing a bound of a variable. This index will be called bound index in the following. For a given active variable with problem index i (note that active variables have problem indices between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd. The following macros can be used to convert bound index into variable problem index and boundtype and vice versa. | |
#define | getLbIndex(idx) (2*(idx)) |
#define | getUbIndex(idx) (2*(idx)+1) |
#define | getVarIndex(idx) ((idx)/2) |
#define | getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER) |
#define | isIndexLowerbound(idx) ((idx) % 2 == 0) |
#define | getOtherBoundIndex(idx) (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1) |
static void | heurdataReset (SCIP_HEURDATA *heurdata) |
static SCIP_RETCODE | dfs (SCIP *scip, int startnode, SCIP_Shortbool *visited, int *dfsstack, int *stacknextedge, int *stacknextcliquevar, int *cliqueexit, int *dfsnodes, int *ndfsnodes) |
static SCIP_RETCODE | topologicalSort (SCIP *scip, int *vbvars, int *nvbvars) |
static SCIP_RETCODE | initializeCandsLists (SCIP *scip, SCIP_HEURDATA *heurdata) |
static SCIP_RETCODE | applyVboundsFixings (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nvbvars, SCIP_Bool tighten, int obj, SCIP_Bool *allobj1, SCIP_Bool *allobj2, SCIP_Bool *backtracked, SCIP_Bool *infeasible) |
static SCIP_RETCODE | createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *newsol, SCIP_SOL *subsol, SCIP_Bool *success) |
static SCIP_RETCODE | setupAndSolveSubscip (SCIP *scip, SCIP *subscip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nvars, SCIP_SOL *sol, SCIP_Longint nstallnodes, SCIP_Real lowerbound, int *nprevars, SCIP_Bool *wasfeas, SCIP_RESULT *result) |
static SCIP_RETCODE | applyVbounds (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vbvars, int nvbvars, SCIP_Bool tighten, int obj, SCIP_Bool *skipobj1, SCIP_Bool *skipobj2, SCIP_RESULT *result) |
static | SCIP_DECL_HEURCOPY (heurCopyVbounds) |
static | SCIP_DECL_HEURFREE (heurFreeVbounds) |
static | SCIP_DECL_HEUREXITSOL (heurExitsolVbounds) |
static | SCIP_DECL_HEUREXEC (heurExecVbounds) |
SCIP_RETCODE | SCIPincludeHeurVbounds (SCIP *scip) |
#define VBOUNDVARIANT_NOOBJ 0x001u |
Definition at line 47 of file heur_vbounds.c.
#define VBOUNDVARIANT_BESTBOUND 0x002u |
Definition at line 48 of file heur_vbounds.c.
#define VBOUNDVARIANT_WORSTBOUND 0x004u |
Definition at line 49 of file heur_vbounds.c.
#define HEUR_NAME "vbounds" |
Definition at line 51 of file heur_vbounds.c.
Referenced by applyVbounds().
#define HEUR_DESC "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood" |
Definition at line 52 of file heur_vbounds.c.
#define HEUR_DISPCHAR 'V' |
Definition at line 53 of file heur_vbounds.c.
#define HEUR_PRIORITY 2500 |
Definition at line 54 of file heur_vbounds.c.
#define HEUR_FREQ 0 |
Definition at line 55 of file heur_vbounds.c.
#define HEUR_FREQOFS 0 |
Definition at line 56 of file heur_vbounds.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 57 of file heur_vbounds.c.
#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE |
Definition at line 58 of file heur_vbounds.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 59 of file heur_vbounds.c.
#define DEFAULT_MAXNODES 5000LL |
maximum number of nodes to regard in the subproblem
Definition at line 61 of file heur_vbounds.c.
#define DEFAULT_MININTFIXINGRATE 0.65 |
minimum percentage of integer variables that have to be fixed
Definition at line 62 of file heur_vbounds.c.
#define DEFAULT_MINMIPFIXINGRATE 0.65 |
minimuskipobjm percentage of variables that have to be fixed within sub-SCIP (integer and continuous)
Definition at line 63 of file heur_vbounds.c.
#define DEFAULT_MINIMPROVE 0.01 |
factor by which vbounds heuristic should at least improve the incumbent
Definition at line 66 of file heur_vbounds.c.
#define DEFAULT_MINNODES 500LL |
minimum number of nodes to regard in the subproblem
Definition at line 69 of file heur_vbounds.c.
#define DEFAULT_NODESOFS 500LL |
number of nodes added to the contingent of the total nodes
Definition at line 70 of file heur_vbounds.c.
#define DEFAULT_NODESQUOT 0.1 |
subproblem nodes in relation to nodes of the original problem
Definition at line 71 of file heur_vbounds.c.
#define DEFAULT_MAXPROPROUNDS 2 |
maximum number of propagation rounds during probing
Definition at line 72 of file heur_vbounds.c.
#define DEFAULT_MAXBACKTRACKS 10 |
maximum number of backtracks during the fixing process
Definition at line 73 of file heur_vbounds.c.
#define DEFAULT_COPYCUTS TRUE |
should all active cuts from the cutpool of the original scip be copied to constraints of the subscip?
Definition at line 74 of file heur_vbounds.c.
#define DEFAULT_USELOCKFIXINGS FALSE |
should more variables be fixed based on variable locks if the fixing rate was not reached?
Definition at line 77 of file heur_vbounds.c.
#define DEFAULT_FEASVARIANT (VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND) |
which variants of the vbounds heuristic that try to stay feasible should be called?
Definition at line 84 of file heur_vbounds.c.
#define DEFAULT_TIGHTENVARIANT (VBOUNDVARIANT_NOOBJ | VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND) |
which tightening variants of the vbounds heuristic should be called?
Definition at line 87 of file heur_vbounds.c.
#define getLbIndex | ( | idx | ) | (2*(idx)) |
Definition at line 137 of file heur_vbounds.c.
Referenced by dfs().
#define getUbIndex | ( | idx | ) | (2*(idx)+1) |
Definition at line 138 of file heur_vbounds.c.
Referenced by dfs().
#define getVarIndex | ( | idx | ) | ((idx)/2) |
Definition at line 139 of file heur_vbounds.c.
Referenced by dfs().
#define getBoundtype | ( | idx | ) | (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER) |
Definition at line 140 of file heur_vbounds.c.
#define isIndexLowerbound | ( | idx | ) | ((idx) % 2 == 0) |
Definition at line 141 of file heur_vbounds.c.
Referenced by dfs().
#define getOtherBoundIndex | ( | idx | ) | (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1) |
Definition at line 142 of file heur_vbounds.c.
Referenced by dfs().
|
static |
reset heuristic data structure
heurdata | structure containing heurdata |
Definition at line 151 of file heur_vbounds.c.
|
static |
performs depth-first-search in the implicitly given directed graph from the given start index
scip | SCIP data structure |
startnode | node to start the depth-first-search |
visited | array to store for each node, whether it was already visited |
dfsstack | array of size number of nodes to store the stack; only needed for performance reasons |
stacknextedge | array of size number of nodes to store the number of adjacent nodes already visited for each node on the stack; only needed for performance reasons |
stacknextcliquevar | array of size number of nodes to store the number of variables already evaluated for the clique currently being evaluated |
cliqueexit | exit node when entering a clique |
dfsnodes | array of nodes that can be reached starting at startnode, in reverse dfs order |
ndfsnodes | pointer to store number of nodes that can be reached starting at startnode |
Definition at line 165 of file heur_vbounds.c.
References FALSE, getLbIndex, getOtherBoundIndex, getUbIndex, getVarIndex, isIndexLowerbound, MAX, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPcliqueGetIndex(), SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisPositive(), SCIPvarGetCliques(), SCIPvarGetIndex(), SCIPvarGetNCliques(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubVars(), SCIPvarIsActive(), SCIPvarIsBinary(), topologicalSort(), and TRUE.
Referenced by topologicalSort().
|
static |
sort the bounds of variables topologically
scip | SCIP data structure |
vbvars | array to store variable bounds in topological order |
nvbvars | pointer to store number of variable bounds in the graph |
Definition at line 395 of file heur_vbounds.c.
References dfs(), initializeCandsLists(), SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPgetNCliques(), and SCIPgetNVars().
Referenced by dfs().
|
static |
initialize candidate lists
scip | original SCIP data structure |
heurdata | structure containing heurdata |
Definition at line 444 of file heur_vbounds.c.
Referenced by topologicalSort().
|
static |
apply variable bound fixing during probing
scip | original SCIP data structure |
heurdata | structure containing heurdata |
vars | variables to fix during probing |
nvbvars | number of variables in the variable bound graph |
tighten | should variables be fixed to cause other fixings? |
obj | should the objective be taken into account? |
allobj1 | pointer to store whether all variables were fixed according to obj=1 scheme |
allobj2 | pointer to store whether all variables were fixed according to obj=2 scheme |
backtracked | was backtracking performed at least once? |
infeasible | pointer to store whether propagation detected infeasibility |
Definition at line 532 of file heur_vbounds.c.
References bound, createNewSol(), FALSE, SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPbacktrackProbing(), SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPdebugMessage, SCIPdebugMsg, SCIPfixVarProbing(), SCIPgetDepth(), SCIPgetNPseudoBranchCands(), SCIPgetProbingDepth(), SCIPisInfinity(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbLocal(), and TRUE.
Referenced by applyVbounds().
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
subvars | the variables of the subproblem |
newsol | working solution |
subsol | solution of the subproblem |
success | used to store whether new solution was found or not |
Definition at line 714 of file heur_vbounds.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPsetSolVals(), SCIPtrySol(), setupAndSolveSubscip(), and TRUE.
Referenced by applyVboundsFixings(), and setupAndSolveSubscip().
|
static |
copy problem to sub-SCIP, solve it, and add solutions
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
heurdata | heuristic data |
vars | variables of the main SCIP |
nvars | number of variables of the main SCIP |
sol | working solution |
nstallnodes | stalling node limit for the sub-SCIP |
lowerbound | lower bound of the main SCIP / current subproblem |
nprevars | pointer to store the number of presolved variables |
wasfeas | pointer to store if a feasible solution was found |
result | pointer to store the result |
Definition at line 757 of file heur_vbounds.c.
References applyVbounds(), createNewSol(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPcheckSol(), SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcopyLimits(), SCIPdebugMsg, SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetNConss(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetSolOrigObj(), SCIPgetSols(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPgetUpperbound(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPisInfinity(), SCIPisParamFixed(), SCIPpresolve(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPsumepsilon(), and TRUE.
Referenced by applyVbounds(), and createNewSol().
|
static |
main procedure of the vbounds heuristic
scip | original SCIP data structure |
heur | heuristic |
heurdata | heuristic data structure |
vbvars | variables to fix during probing |
nvbvars | number of variables to fix |
tighten | should variables be fixed to cause other fixings? |
obj | should the objective be taken into account? |
skipobj1 | pointer to store whether the run with obj=1 can be skipped, or NULL |
skipobj2 | pointer to store whether the run with obj=2 can be skipped, or NULL |
result | pointer to store the result |
Definition at line 942 of file heur_vbounds.c.
References applyVboundsFixings(), FALSE, HEUR_NAME, SCIP_Bool, SCIP_CALL, SCIP_DECL_HEURCOPY(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LPSOLSTAT_ERROR, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPapplyLockFixings(), SCIPcheckCopyLimits(), SCIPcheckSol(), SCIPclockGetTime(), SCIPconstructLP(), SCIPcreate(), SCIPcreateClock(), SCIPcreateSol(), SCIPcutoffNode(), SCIPdebugMsg, SCIPenableVarHistory(), SCIPendProbing(), SCIPflushLP(), SCIPfree(), SCIPfreeClock(), SCIPfreeSol(), SCIPgetCurrentNode(), SCIPgetLowerbound(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), SCIPgetNNodes(), SCIPgetNPseudoBranchCands(), SCIPgetSolOrigObj(), SCIPgetSolvingTime(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPinProbing(), SCIPisLPConstructed(), SCIPisStopped(), SCIPlinkLPSol(), SCIPnodeGetNumber(), SCIProundSol(), SCIPsolveProbingLP(), SCIPstartClock(), SCIPstartProbing(), SCIPstatistic, SCIPstatisticMessage, SCIPstopClock(), SCIPtrySol(), SCIPwarningMessage(), setupAndSolveSubscip(), and TRUE.
Referenced by setupAndSolveSubscip().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 1248 of file heur_vbounds.c.
Referenced by applyVbounds().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 1262 of file heur_vbounds.c.
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 1278 of file heur_vbounds.c.
|
static |
execution method of primal heuristic
Definition at line 1304 of file heur_vbounds.c.