Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood.

Author
Timo Berthold
Stefan Heinz
Jens Schulz
Gerald Gamrath

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.

Macros

#define VBOUNDVARIANT_NOOBJ   0x001u
 
#define VBOUNDVARIANT_BESTBOUND   0x002u
 
#define VBOUNDVARIANT_WORSTBOUND   0x004u
 
#define HEUR_NAME   "vbounds"
 
#define HEUR_DESC   "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood"
 
#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_PROP
 
#define HEUR_PRIORITY   2500
 
#define HEUR_FREQ   0
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE
 
#define HEUR_USESSUBSCIP   TRUE
 
#define DEFAULT_MAXNODES   5000LL
 
#define DEFAULT_MININTFIXINGRATE   0.65
 
#define DEFAULT_MINMIPFIXINGRATE   0.65
 
#define DEFAULT_MINIMPROVE   0.01
 
#define DEFAULT_MINNODES   500LL
 
#define DEFAULT_NODESOFS   500LL
 
#define DEFAULT_NODESQUOT   0.1
 
#define DEFAULT_MAXPROPROUNDS   2
 
#define DEFAULT_MAXBACKTRACKS   10
 
#define DEFAULT_COPYCUTS   TRUE
 
#define DEFAULT_USELOCKFIXINGS   FALSE
 
#define DEFAULT_FEASVARIANT   (VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
 
#define DEFAULT_TIGHTENVARIANT   (VBOUNDVARIANT_NOOBJ | VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
 

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 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)
 

Macro Definition Documentation

◆ VBOUNDVARIANT_NOOBJ

#define VBOUNDVARIANT_NOOBJ   0x001u

Definition at line 69 of file heur_vbounds.c.

◆ VBOUNDVARIANT_BESTBOUND

#define VBOUNDVARIANT_BESTBOUND   0x002u

Definition at line 70 of file heur_vbounds.c.

◆ VBOUNDVARIANT_WORSTBOUND

#define VBOUNDVARIANT_WORSTBOUND   0x004u

Definition at line 71 of file heur_vbounds.c.

◆ HEUR_NAME

#define HEUR_NAME   "vbounds"

Definition at line 73 of file heur_vbounds.c.

Referenced by applyVbounds().

◆ HEUR_DESC

#define HEUR_DESC   "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood"

Definition at line 74 of file heur_vbounds.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_PROP

Definition at line 75 of file heur_vbounds.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   2500

Definition at line 76 of file heur_vbounds.c.

◆ HEUR_FREQ

#define HEUR_FREQ   0

Definition at line 77 of file heur_vbounds.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 78 of file heur_vbounds.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 79 of file heur_vbounds.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

Definition at line 80 of file heur_vbounds.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 81 of file heur_vbounds.c.

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   5000LL

maximum number of nodes to regard in the subproblem

Definition at line 83 of file heur_vbounds.c.

◆ DEFAULT_MININTFIXINGRATE

#define DEFAULT_MININTFIXINGRATE   0.65

minimum percentage of integer variables that have to be fixed

Definition at line 84 of file heur_vbounds.c.

◆ DEFAULT_MINMIPFIXINGRATE

#define DEFAULT_MINMIPFIXINGRATE   0.65

minimuskipobjm percentage of variables that have to be fixed within sub-SCIP (integer and continuous)

Definition at line 85 of file heur_vbounds.c.

◆ DEFAULT_MINIMPROVE

#define DEFAULT_MINIMPROVE   0.01

factor by which vbounds heuristic should at least improve the incumbent

Definition at line 88 of file heur_vbounds.c.

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   500LL

minimum number of nodes to regard in the subproblem

Definition at line 91 of file heur_vbounds.c.

◆ DEFAULT_NODESOFS

#define DEFAULT_NODESOFS   500LL

number of nodes added to the contingent of the total nodes

Definition at line 92 of file heur_vbounds.c.

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT   0.1

subproblem nodes in relation to nodes of the original problem

Definition at line 93 of file heur_vbounds.c.

◆ DEFAULT_MAXPROPROUNDS

#define DEFAULT_MAXPROPROUNDS   2

maximum number of propagation rounds during probing

Definition at line 94 of file heur_vbounds.c.

◆ DEFAULT_MAXBACKTRACKS

#define DEFAULT_MAXBACKTRACKS   10

maximum number of backtracks during the fixing process

Definition at line 95 of file heur_vbounds.c.

◆ DEFAULT_COPYCUTS

#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 96 of file heur_vbounds.c.

◆ DEFAULT_USELOCKFIXINGS

#define DEFAULT_USELOCKFIXINGS   FALSE

should more variables be fixed based on variable locks if the fixing rate was not reached?

Definition at line 99 of file heur_vbounds.c.

◆ DEFAULT_FEASVARIANT

#define DEFAULT_FEASVARIANT   (VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)

which variants of the vbounds heuristic that try to stay feasible should be called?

Definition at line 106 of file heur_vbounds.c.

◆ DEFAULT_TIGHTENVARIANT

#define DEFAULT_TIGHTENVARIANT   (VBOUNDVARIANT_NOOBJ | VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)

which tightening variants of the vbounds heuristic should be called?

Definition at line 109 of file heur_vbounds.c.

◆ getLbIndex

#define getLbIndex (   idx)    (2*(idx))

Definition at line 156 of file heur_vbounds.c.

Referenced by dfs().

◆ getUbIndex

#define getUbIndex (   idx)    (2*(idx)+1)

Definition at line 157 of file heur_vbounds.c.

Referenced by dfs().

◆ getVarIndex

#define getVarIndex (   idx)    ((idx)/2)

Definition at line 158 of file heur_vbounds.c.

Referenced by dfs().

◆ getBoundtype

#define getBoundtype (   idx)    (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)

Definition at line 159 of file heur_vbounds.c.

◆ isIndexLowerbound

#define isIndexLowerbound (   idx)    ((idx) % 2 == 0)

Definition at line 160 of file heur_vbounds.c.

Referenced by dfs().

◆ getOtherBoundIndex

#define getOtherBoundIndex (   idx)    (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1)

Definition at line 161 of file heur_vbounds.c.

Referenced by dfs().

Function Documentation

◆ heurdataReset()

static void heurdataReset ( SCIP_HEURDATA heurdata)
static

reset heuristic data structure

Parameters
heurdatastructure containing heurdata

Definition at line 170 of file heur_vbounds.c.

◆ dfs()

static SCIP_RETCODE dfs ( SCIP scip,
int  startnode,
SCIP_Shortbool visited,
int *  dfsstack,
int *  stacknextedge,
int *  stacknextcliquevar,
int *  cliqueexit,
int *  dfsnodes,
int *  ndfsnodes 
)
static

performs depth-first-search in the implicitly given directed graph from the given start index

Parameters
scipSCIP data structure
startnodenode to start the depth-first-search
visitedarray to store for each node, whether it was already visited
dfsstackarray of size number of nodes to store the stack; only needed for performance reasons
stacknextedgearray 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
stacknextcliquevararray of size number of nodes to store the number of variables already evaluated for the clique currently being evaluated
cliqueexitexit node when entering a clique
dfsnodesarray of nodes that can be reached starting at startnode, in reverse dfs order
ndfsnodespointer to store number of nodes that can be reached starting at startnode

Definition at line 184 of file heur_vbounds.c.

References FALSE, getLbIndex, getOtherBoundIndex, getUbIndex, getVarIndex, isIndexLowerbound, MAX, NULL, 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().

◆ topologicalSort()

static SCIP_RETCODE topologicalSort ( SCIP scip,
int *  vbvars,
int *  nvbvars 
)
static

sort the bounds of variables topologically

Parameters
scipSCIP data structure
vbvarsarray to store variable bounds in topological order
nvbvarspointer to store number of variable bounds in the graph

Definition at line 414 of file heur_vbounds.c.

References dfs(), initializeCandsLists(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPgetNCliques(), and SCIPgetNVars().

Referenced by dfs().

◆ initializeCandsLists()

static SCIP_RETCODE initializeCandsLists ( SCIP scip,
SCIP_HEURDATA heurdata 
)
static

initialize candidate lists

Parameters
sciporiginal SCIP data structure
heurdatastructure containing heurdata

Definition at line 462 of file heur_vbounds.c.

Referenced by topologicalSort().

◆ applyVboundsFixings()

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

apply variable bound fixing during probing

Parameters
sciporiginal SCIP data structure
heurdatastructure containing heurdata
varsvariables to fix during probing
nvbvarsnumber of variables in the variable bound graph
tightenshould variables be fixed to cause other fixings?
objshould the objective be taken into account?
allobj1pointer to store whether all variables were fixed according to obj=1 scheme
allobj2pointer to store whether all variables were fixed according to obj=2 scheme
backtrackedwas backtracking performed at least once?
infeasiblepointer to store whether propagation detected infeasibility

Definition at line 550 of file heur_vbounds.c.

References bound, FALSE, NULL, 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(), setupAndSolveSubscip(), and TRUE.

Referenced by applyVbounds().

◆ setupAndSolveSubscip()

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

copy problem to sub-SCIP, solve it, and add solutions

Parameters
sciporiginal SCIP data structure
subscipSCIP structure of the subproblem
heurheuristic
varsvariables of the main SCIP
nvarsnumber of variables of the main SCIP
nstallnodesstalling node limit for the sub-SCIP
lowerboundlower bound of the main SCIP / current subproblem
nprevarspointer to store the number of presolved variables
wasfeaspointer to store if a feasible solution was found
resultpointer to store the result

Definition at line 731 of file heur_vbounds.c.

References applyVbounds(), FALSE, NULL, SCIP_CALL, SCIP_CALL_ABORT, SCIP_FOUNDSOL, 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(), and TRUE.

Referenced by applyVbounds(), and applyVboundsFixings().

◆ applyVbounds()

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

main procedure of the vbounds heuristic

Parameters
sciporiginal SCIP data structure
heurheuristic
heurdataheuristic data structure
vbvarsvariables to fix during probing
nvbvarsnumber of variables to fix
tightenshould variables be fixed to cause other fixings?
objshould the objective be taken into account?
skipobj1pointer to store whether the run with obj=1 can be skipped, or NULL
skipobj2pointer to store whether the run with obj=2 can be skipped, or NULL
resultpointer to store the result

Definition at line 892 of file heur_vbounds.c.

References applyVboundsFixings(), FALSE, HEUR_NAME, NULL, 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_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(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPinProbing(), SCIPisLPConstructed(), SCIPisLPSolBasic(), SCIPisStopped(), SCIPlinkLPSol(), SCIPnodeGetNumber(), SCIProundSol(), SCIPsnprintfProbingStats(), SCIPsolveProbingLP(), SCIPstartClock(), SCIPstartProbing(), SCIPstatistic, SCIPstatisticMessage, SCIPstopClock(), SCIPtrySol(), SCIPverbMessage(), SCIPwarningMessage(), setupAndSolveSubscip(), and TRUE.

Referenced by setupAndSolveSubscip().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyVbounds  )
static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 1211 of file heur_vbounds.c.

Referenced by applyVbounds().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeVbounds  )
static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 1225 of file heur_vbounds.c.

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolVbounds  )
static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 1241 of file heur_vbounds.c.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecVbounds  )
static

execution method of primal heuristic

Definition at line 1267 of file heur_vbounds.c.