Scippy

SCIP

Solving Constraint Integer Programs

Macros
heur_vbounds.c File Reference

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 <assert.h>
#include <string.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/heur_vbounds.h"

Go to the source code of this file.

Macros

#define HEUR_NAME   "vbounds"
 
#define HEUR_DESC   "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood"
 
#define HEUR_DISPCHAR   'V'
 
#define HEUR_PRIORITY   -1106000
 
#define HEUR_FREQ   -1
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE
 
#define HEUR_USESSUBSCIP   TRUE
 
#define DEFAULT_MAXNODES   5000LL /* maximum number of nodes to regard in the subproblem */
 
#define DEFAULT_MINFIXINGRATE   0.25 /* minimum percentage of integer variables that have to be fixed */
 
#define DEFAULT_MINIMPROVE   0.01 /* factor by which vbounds heuristic should at least improve the incumbent */
 
#define DEFAULT_MINNODES   500LL /* minimum number of nodes to regard in the subproblem */
 
#define DEFAULT_NODESOFS   500LL /* number of nodes added to the contingent of the total nodes */
 
#define DEFAULT_NODESQUOT   0.1 /* subproblem nodes in relation to nodes of the original problem */
 
#define DEFAULT_MAXPROPROUNDS   2 /* maximum number of propagation rounds during probing */
 
#define DEFAULT_COPYCUTS   TRUE
 

Propagator defines

The propagator 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)
 
static void heurdataReset (SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE dfs (SCIP *scip, int startnode, SCIP_Bool *visited, int *dfsstack, int *stacknextedge, 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, SCIP_Bool obj, SCIP_Bool *infeasible, SCIP_VAR **lastvar, SCIP_Bool *fixedtolb)
 
static SCIP_RETCODE createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *newsol, SCIP_SOL *subsol, SCIP_Bool *success)
 
static SCIP_RETCODE applyVbounds (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vbvars, int nvbvars, SCIP_Bool tighten, SCIP_Bool obj, 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

◆ HEUR_NAME

#define HEUR_NAME   "vbounds"

Definition at line 46 of file heur_vbounds.c.

Referenced by applyVbounds(), and SCIPincludeHeurVbounds().

◆ HEUR_DESC

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

Definition at line 47 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'V'

Definition at line 48 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -1106000

Definition at line 49 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 50 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 51 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 52 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

Definition at line 53 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 54 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   5000LL /* maximum number of nodes to regard in the subproblem */

Definition at line 56 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ DEFAULT_MINFIXINGRATE

#define DEFAULT_MINFIXINGRATE   0.25 /* minimum percentage of integer variables that have to be fixed */

Definition at line 57 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ DEFAULT_MINIMPROVE

#define DEFAULT_MINIMPROVE   0.01 /* factor by which vbounds heuristic should at least improve the incumbent */

Definition at line 58 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   500LL /* minimum number of nodes to regard in the subproblem */

Definition at line 59 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ DEFAULT_NODESOFS

#define DEFAULT_NODESOFS   500LL /* number of nodes added to the contingent of the total nodes */

Definition at line 60 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT   0.1 /* subproblem nodes in relation to nodes of the original problem */

Definition at line 61 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ DEFAULT_MAXPROPROUNDS

#define DEFAULT_MAXPROPROUNDS   2 /* maximum number of propagation rounds during probing */

Definition at line 62 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ 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 63 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

◆ getLbIndex

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

Definition at line 106 of file heur_vbounds.c.

Referenced by dfs().

◆ getUbIndex

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

Definition at line 107 of file heur_vbounds.c.

Referenced by dfs().

◆ getVarIndex

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

Definition at line 108 of file heur_vbounds.c.

Referenced by dfs(), and initializeCandsLists().

◆ getBoundtype

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

Definition at line 109 of file heur_vbounds.c.

Referenced by initializeCandsLists().

◆ isIndexLowerbound

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

Definition at line 110 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 123 of file heur_vbounds.c.

References dfs(), FALSE, and NULL.

Referenced by SCIPincludeHeurVbounds().

◆ dfs()

static SCIP_RETCODE dfs ( SCIP *  scip,
int  startnode,
SCIP_Bool *  visited,
int *  dfsstack,
int *  stacknextedge,
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
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 137 of file heur_vbounds.c.

References FALSE, getLbIndex, getUbIndex, getVarIndex, isIndexLowerbound, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPgetNVars(), SCIPgetVars(), SCIPisPositive(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubVars(), SCIPvarIsActive(), topologicalSort(), and TRUE.

Referenced by heurdataReset(), and 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
nvbvarsarray to store number of variable bounds in the graph

Definition at line 255 of file heur_vbounds.c.

References BMSclearMemoryArray, dfs(), initializeCandsLists(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPgetNVars().

Referenced by dfs(), and initializeCandsLists().

◆ 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 298 of file heur_vbounds.c.

References applyVboundsFixings(), getBoundtype, getVarIndex, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcaptureVar(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetProbName(), SCIPgetVars(), SCIPstatisticMessage, topologicalSort(), and TRUE.

Referenced by topologicalSort().

◆ applyVboundsFixings()

static SCIP_RETCODE applyVboundsFixings ( SCIP *  scip,
SCIP_HEURDATA *  heurdata,
SCIP_VAR **  vars,
int  nvbvars,
SCIP_Bool  tighten,
SCIP_Bool  obj,
SCIP_Bool *  infeasible,
SCIP_VAR **  lastvar,
SCIP_Bool *  fixedtolb 
)
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?
infeasiblepointer to store whether problem is infeasible
lastvarlast fixed variable
fixedtolbwas last fixed variable fixed to its lower bound?

Definition at line 355 of file heur_vbounds.c.

References bound, createNewSol(), FALSE, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPdebugMsg, SCIPfixVarProbing(), SCIPgetDepth(), SCIPgetNPseudoBranchCands(), SCIPisInfinity(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbLocal(), and TRUE.

Referenced by applyVbounds(), and initializeCandsLists().

◆ createNewSol()

static SCIP_RETCODE createNewSol ( SCIP *  scip,
SCIP *  subscip,
SCIP_VAR **  subvars,
SCIP_SOL *  newsol,
SCIP_SOL *  subsol,
SCIP_Bool *  success 
)
static

creates a new solution for the original problem by copying the solution of the subproblem

Parameters
sciporiginal SCIP data structure
subscipSCIP structure of the subproblem
subvarsthe variables of the subproblem
newsolworking solution
subsolsolution of the subproblem
successused to store whether new solution was found or not

Definition at line 462 of file heur_vbounds.c.

References applyVbounds(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPsetSolVals(), SCIPtrySol(), 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,
SCIP_Bool  obj,
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?
resultpointer to store the result

Definition at line 505 of file heur_vbounds.c.

References applyVboundsFixings(), createNewSol(), FALSE, HEUR_NAME, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, 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_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPblkmem(), SCIPcheckCopyLimits(), SCIPclearSol(), SCIPclockGetTime(), SCIPconstructLP(), SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcopyLimits(), SCIPcreate(), SCIPcreateClock(), SCIPcreateSol(), SCIPcutoffNode(), SCIPdebugMsg, SCIPendProbing(), SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfindNodesel(), SCIPfixVarProbing(), SCIPflushLP(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeClock(), SCIPfreeSol(), SCIPgetCurrentNode(), SCIPgetLowerbound(), SCIPgetLPSolstat(), SCIPgetNConss(), SCIPgetNLPIterations(), SCIPgetNNodes(), SCIPgetNPseudoBranchCands(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetProbingDepth(), SCIPgetSolOrigObj(), SCIPgetSols(), SCIPgetSolvingTime(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPisInfinity(), SCIPisLPConstructed(), SCIPisParamFixed(), SCIPisStopped(), SCIPlinkLPSol(), SCIPnodeGetNumber(), SCIPpresolve(), SCIPprintStatistics(), SCIPpropagateProbing(), SCIProundSol(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPsolveProbingLP(), SCIPstartClock(), SCIPstartProbing(), SCIPstatistic, SCIPstatisticMessage, SCIPstopClock(), SCIPsumepsilon(), SCIPtrySol(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPwarningMessage(), and TRUE.

Referenced by createNewSol().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyVbounds  )
static

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

Definition at line 937 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 951 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 967 of file heur_vbounds.c.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecVbounds  )
static

execution method of primal heuristic

Definition at line 993 of file heur_vbounds.c.