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 "blockmemshell/memory.h"
#include "scip/heur_locks.h"
#include "scip/heur_vbounds.h"
#include "scip/pub_heur.h"
#include "scip/pub_implics.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.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_probing.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.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) |
#define | getUbIndex(idx) |
#define | getVarIndex(idx) |
#define | getBoundtype(idx) |
#define | isIndexLowerbound(idx) |
#define | getOtherBoundIndex(idx) |
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 | setupAndSolveSubscip (SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **vars, int nvars, 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 78 of file heur_vbounds.c.
Referenced by SCIP_DECL_HEUREXEC().
#define VBOUNDVARIANT_BESTBOUND 0x002u |
Definition at line 79 of file heur_vbounds.c.
Referenced by SCIP_DECL_HEUREXEC().
#define VBOUNDVARIANT_WORSTBOUND 0x004u |
Definition at line 80 of file heur_vbounds.c.
Referenced by SCIP_DECL_HEUREXEC().
#define HEUR_NAME "vbounds" |
Definition at line 82 of file heur_vbounds.c.
#define HEUR_DESC "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood" |
Definition at line 83 of file heur_vbounds.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP |
Definition at line 84 of file heur_vbounds.c.
#define HEUR_PRIORITY 2500 |
Definition at line 85 of file heur_vbounds.c.
#define HEUR_FREQ 0 |
Definition at line 86 of file heur_vbounds.c.
#define HEUR_FREQOFS 0 |
Definition at line 87 of file heur_vbounds.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 88 of file heur_vbounds.c.
#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE |
Definition at line 89 of file heur_vbounds.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 90 of file heur_vbounds.c.
#define DEFAULT_MAXNODES 5000LL |
maximum number of nodes to regard in the subproblem
Definition at line 92 of file heur_vbounds.c.
#define DEFAULT_MININTFIXINGRATE 0.65 |
minimum percentage of integer variables that have to be fixed
Definition at line 93 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 94 of file heur_vbounds.c.
#define DEFAULT_MINIMPROVE 0.01 |
factor by which vbounds heuristic should at least improve the incumbent
Definition at line 96 of file heur_vbounds.c.
#define DEFAULT_MINNODES 500LL |
minimum number of nodes to regard in the subproblem
Definition at line 98 of file heur_vbounds.c.
#define DEFAULT_NODESOFS 500LL |
number of nodes added to the contingent of the total nodes
Definition at line 99 of file heur_vbounds.c.
#define DEFAULT_NODESQUOT 0.1 |
subproblem nodes in relation to nodes of the original problem
Definition at line 100 of file heur_vbounds.c.
#define DEFAULT_MAXPROPROUNDS 2 |
maximum number of propagation rounds during probing
Definition at line 101 of file heur_vbounds.c.
#define DEFAULT_MAXBACKTRACKS 10 |
maximum number of backtracks during the fixing process
Definition at line 102 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 103 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 105 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 110 of file heur_vbounds.c.
Referenced by SCIPincludeHeurVbounds().
#define DEFAULT_TIGHTENVARIANT (VBOUNDVARIANT_NOOBJ | VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND) |
which tightening variants of the vbounds heuristic should be called?
Definition at line 113 of file heur_vbounds.c.
Referenced by SCIPincludeHeurVbounds().
#define getLbIndex | ( | idx | ) |
#define getUbIndex | ( | idx | ) |
#define getVarIndex | ( | idx | ) |
Definition at line 162 of file heur_vbounds.c.
Referenced by computeGradient(), dfs(), initializeCandsLists(), and SCIP_DECL_EVENTEXEC().
#define getBoundtype | ( | idx | ) |
Definition at line 163 of file heur_vbounds.c.
Referenced by initializeCandsLists().
#define isIndexLowerbound | ( | idx | ) |
Definition at line 164 of file heur_vbounds.c.
Referenced by dfs(), and SCIP_DECL_EVENTEXEC().
#define getOtherBoundIndex | ( | idx | ) |
Definition at line 165 of file heur_vbounds.c.
Referenced by dfs().
|
static |
reset heuristic data structure
heurdata | structure containing heurdata |
Definition at line 174 of file heur_vbounds.c.
References FALSE, heurdata, and NULL.
Referenced by SCIP_DECL_HEUREXITSOL(), and SCIPincludeHeurVbounds().
|
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 188 of file heur_vbounds.c.
References assert(), FALSE, getLbIndex, getOtherBoundIndex, getUbIndex, getVarIndex, i, isIndexLowerbound, MAX, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_Shortbool, SCIP_VARTYPE_CONTINUOUS, SCIPcliqueGetIndex(), SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisPositive(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubVars(), SCIPvarIsActive(), SCIPvarIsBinary(), TRUE, and vars.
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 417 of file heur_vbounds.c.
References assert(), dfs(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPgetNCliques(), and SCIPgetNVars().
Referenced by initializeCandsLists().
|
static |
initialize candidate lists
scip | original SCIP data structure |
heurdata | structure containing heurdata |
Definition at line 465 of file heur_vbounds.c.
References assert(), getBoundtype, getVarIndex, heurdata, MIN, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcaptureVar(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLowerbound(), SCIPgetNBinVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNSols(), SCIPgetProbName(), SCIPgetUpperbound(), SCIPgetVars(), SCIPinfinity(), SCIPisInfinity(), SCIPstatisticMessage, SCIPsumepsilon(), SCIPvarIsIntegral(), topologicalSort(), TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
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 553 of file heur_vbounds.c.
References assert(), backtracked, bound, FALSE, heurdata, NULL, obj, 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(), TRUE, var, and vars.
Referenced by applyVbounds().
|
static |
copy problem to sub-SCIP, solve it, and add solutions
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
heur | heuristic |
vars | variables of the main SCIP |
nvars | number of variables of the main SCIP |
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 734 of file heur_vbounds.c.
References assert(), FALSE, heurdata, i, MIN, NULL, nvars, result, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcopyLimits(), SCIPdebugMsg, SCIPfindBranchrule(), SCIPfreeBufferArray, SCIPgetNConss(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPgetUpperbound(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPisInfinity(), SCIPisParamFixed(), SCIPpresolve(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPsumepsilon(), SCIPtranslateSubSols(), TRUE, and vars.
Referenced by applyVbounds().
|
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 895 of file heur_vbounds.c.
References applyVboundsFixings(), assert(), backtracked, cutoff, FALSE, HEUR_NAME, heurdata, lperror, MIN, NULL, nvars, obj, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_ERROR, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIPapplyLockFixings(), SCIPcheckCopyLimits(), SCIPcheckSol(), SCIPclockGetTime(), SCIPconstructLP(), SCIPcreate(), SCIPcreateClock(), SCIPcreateSol(), SCIPcutoffNode(), SCIPdebugMsg, SCIPenableVarHistory(), SCIPendProbing(), SCIPflushLP(), SCIPfree(), SCIPfreeClock(), SCIPfreeSol(), SCIPgetCurrentNode(), SCIPgetLowerbound(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNLPCols(), SCIPgetNLPIterations(), SCIPgetNNodes(), SCIPgetNPseudoBranchCands(), SCIPgetNUnfixedLPCols(), SCIPgetNVars(), SCIPgetSolOrigObj(), SCIPgetSolvingTime(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPinProbing(), SCIPisLPConstructed(), SCIPisLPSolBasic(), SCIPisStopped(), SCIPlinkLPSol(), SCIPnodeGetNumber(), SCIProundSol(), SCIPsnprintfProbingStats(), SCIPsolveProbingLP(), SCIPstartClock(), SCIPstartProbing(), SCIPstatistic, SCIPstatisticMessage, SCIPstopClock(), SCIPtrySol(), SCIPverbMessage(), SCIPwarningMessage(), setupAndSolveSubscip(), sol, TRUE, valid, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 1214 of file heur_vbounds.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurVbounds().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 1228 of file heur_vbounds.c.
References heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 1244 of file heur_vbounds.c.
References assert(), heurdata, heurdataReset(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, SCIPheurGetData(), and SCIPreleaseVar().
|
static |
execution method of primal heuristic
Definition at line 1270 of file heur_vbounds.c.
References applyVbounds(), assert(), FALSE, heurdata, initializeCandsLists(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPgetBoolParam(), SCIPgetNPseudoBranchCands(), SCIPheurGetData(), SCIPisParamFixed(), SCIPsetBoolParam(), TRUE, VBOUNDVARIANT_BESTBOUND, VBOUNDVARIANT_NOOBJ, and VBOUNDVARIANT_WORSTBOUND.