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

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.5 /* 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

Functions
static	SCIP_DECL_HASHGETKEY (hashGetKeyVar)
static	SCIP_DECL_HASHKEYEQ (hashKeyEqVar)
static	SCIP_DECL_HASHKEYVAL (hashKeyValVar)
static void	heurdataReset (SCIP_HEURDATA *heurdata)
static void	getVariableBounds (SCIP_VAR *var, SCIP_VAR ***vbvars, int *nvbvars, SCIP_Bool lowerbound)
static SCIP_RETCODE	depthFirstSearch (SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *varPosMap, SCIP_VAR **usedvars, int *nusedvars, SCIP_HASHTABLE *connected, SCIP_VAR **sortedvars, int *nsortedvars, SCIP_Bool lowerbound)
static SCIP_RETCODE	createTopoSortedVars (SCIP *scip, SCIP_VAR **vars, int nvars, SCIP_HASHMAP *varPosMap, SCIP_VAR **usedvars, int *nusedvars, SCIP_VAR **topovars, int *ntopovars, SCIP_Bool lowerbound)
static SCIP_RETCODE	initializeCandsLists (SCIP *scip, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	applyVboundsFixings (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nlbvars, int nubvars, SCIP_SOL *sol, SCIP_Bool *infeasible, SCIP_RESULT *result)
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 **probvars, int nlbvars, int nubvars, 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

#define HEUR_NAME   "vbounds"

Definition at line 33 of file heur_vbounds.c.

Referenced by applyVbounds(), SCIP_DECL_HEURCOPY(), and SCIPincludeHeurVbounds().

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

Definition at line 34 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

#define HEUR_DISPCHAR   'V'

Definition at line 35 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

#define HEUR_PRIORITY   -1106000

Definition at line 36 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

#define HEUR_FREQ   -1

Definition at line 37 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

#define HEUR_FREQOFS   0

Definition at line 38 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

#define HEUR_MAXDEPTH   -1

Definition at line 39 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

Definition at line 40 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 41 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

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

Definition at line 43 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

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

Definition at line 44 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

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

Definition at line 45 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

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

Definition at line 46 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

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

Definition at line 47 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

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

Definition at line 48 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

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

Definition at line 49 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

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

Referenced by SCIPincludeHeurVbounds().

Function Documentation

static SCIP_DECL_HASHGETKEY ( hashGetKeyVar  )

static

hash key retrieval function for variables

Definition at line 92 of file heur_vbounds.c.

static SCIP_DECL_HASHKEYEQ ( hashKeyEqVar  )

static

returns TRUE iff the indices of both variables are equal

Definition at line 99 of file heur_vbounds.c.

References FALSE, and TRUE.

static SCIP_DECL_HASHKEYVAL ( hashKeyValVar  )

static

returns the hash value of the key

Definition at line 108 of file heur_vbounds.c.

References SCIPvarGetIndex().

static void heurdataReset ( SCIP_HEURDATA *  heurdata )

static

reset heuristic data structure

Parameters

heurdata

structure containing heurdata

Definition at line 121 of file heur_vbounds.c.

References FALSE, and NULL.

Referenced by SCIP_DECL_HEUREXITSOL(), and SCIPincludeHeurVbounds().

static void getVariableBounds ( SCIP_VAR *  var, SCIP_VAR ***  vbvars, int *  nvbvars, SCIP_Bool  lowerbound  )

static

gets the requested variables bounds

Parameters

var	variable to get the variable bounds from
vbvars	pointer to store the variable bound array
nvbvars	pointer to store the number of variable bounds
lowerbound	variable lower bounds? (otherwise variable upper bound)

Definition at line 138 of file heur_vbounds.c.

References SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetVlbVars(), and SCIPvarGetVubVars().

Referenced by createTopoSortedVars(), and depthFirstSearch().

static SCIP_RETCODE depthFirstSearch ( SCIP *  scip, SCIP_VAR *  var, SCIP_HASHMAP *  varPosMap, SCIP_VAR **  usedvars, int *  nusedvars, SCIP_HASHTABLE *  connected, SCIP_VAR **  sortedvars, int *  nsortedvars, SCIP_Bool  lowerbound  )

static

perform depth-first-search from the given variable using the variable lower or upper bounds of the variable

Parameters

scip	SCIP data structure
var	variable to start the depth-first-search
varPosMap	mapping a variable to its position in the (used) variable array, or NULL
usedvars	array of variables which are involved in the propagation, or NULL
nusedvars	number of variables which are involved in the propagation, or NULL
connected	hash table storing if a node was already visited
sortedvars	array that will contain the topological sorted variables
nsortedvars	pointer to store the number of already collects variables in the sorted variables array
lowerbound	depth-first-search with respect to the variable lower bounds, otherwise variable upper bound

Definition at line 161 of file heur_vbounds.c.

References getVariableBounds(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetProbvarSum(), SCIPhashmapExists(), SCIPhashmapInsert(), SCIPhashtableExists(), SCIPhashtableRemove(), SCIPvarGetName(), SCIPvarGetProbindex(), and SCIPvarIsActive().

Referenced by createTopoSortedVars().

static SCIP_RETCODE createTopoSortedVars ( SCIP *  scip, SCIP_VAR **  vars, int  nvars, SCIP_HASHMAP *  varPosMap, SCIP_VAR **  usedvars, int *  nusedvars, SCIP_VAR **  topovars, int *  ntopovars, SCIP_Bool  lowerbound  )

static

create a topological sorted variable array of the given variables and stores if (needed) the involved variables into the corresponding variable array and hash map

Note

: for all arrays and the hash map (if requested) you need to allocate enough memory before calling this method

Parameters

scip	SCIP data structure
vars	variable which we want sort
nvars	number of variables
varPosMap	mapping a variable to its position in the (used) variable array, or NULL
usedvars	array of variables which are involved in the propagation, or NULL
nusedvars	number of variables which are involved in the propagation, or NULL
topovars	array where the topological sorted variables are stored
ntopovars	pointer to store the number of topological sorted variables
lowerbound	topological sorted with respect to the variable lower bounds, otherwise variable upper bound

Definition at line 252 of file heur_vbounds.c.

References depthFirstSearch(), getVariableBounds(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPvarGetName(), and SCIPvarIsActive().

Referenced by initializeCandsLists().

static SCIP_RETCODE initializeCandsLists ( SCIP *  scip, SCIP_HEURDATA *  heurdata  )

static

initialize candidate lists

Parameters

scip	original SCIP data structure
heurdata	structure containing heurdata

Definition at line 367 of file heur_vbounds.c.

References createTopoSortedVars(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPcaptureVar(), SCIPdebugMessage, SCIPduplicateMemoryArray, SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetProbName(), SCIPgetVars(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPisGE(), SCIPisLE(), SCIPstatisticMessage, SCIPvarGetObj(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE applyVboundsFixings ( SCIP *  scip, SCIP_HEURDATA *  heurdata, SCIP_VAR **  vars, int  nlbvars, int  nubvars, SCIP_SOL *  sol, SCIP_Bool *  infeasible, SCIP_RESULT *  result  )

static

apply variable bound fixing during probing

Parameters

scip	original SCIP data structure
heurdata	structure containing heurdata
vars	variables to fix during probing
nlbvars	number of variables to use the lower bound
nubvars	number of variables to use the upper bound
sol	working solution
infeasible	pointer to store whether problem is infeasible
result	pointer to store the result (solution found)

Definition at line 495 of file heur_vbounds.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPdebugMessage, SCIPfixVarProbing(), SCIPgetNPseudoBranchCands(), SCIPgetSolOrigObj(), SCIPisStopped(), SCIPlinkCurrentSol(), SCIPpropagateProbing(), SCIProundSol(), SCIPtrySol(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), and TRUE.

Referenced by applyVbounds().

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

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

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPsetSolVals(), SCIPtrySol(), and TRUE.

Referenced by applyVbounds().

static SCIP_RETCODE applyVbounds ( SCIP *  scip, SCIP_HEUR *  heur, SCIP_HEURDATA *  heurdata, SCIP_VAR **  probvars, int  nlbvars, int  nubvars, SCIP_RESULT *  result  )

static

main procedure of the vbounds heuristic

Parameters

scip	original SCIP data structure
heur	heuristic
heurdata	heuristic data structure
probvars	variables to fix during probing
nlbvars	number of variables to use the lower bound
nubvars	number of variables to use the upper bound
result	pointer to store the result

Definition at line 614 of file heur_vbounds.c.

References applyVboundsFixings(), createNewSol(), FALSE, HEUR_NAME, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPcopy(), SCIPcopyCuts(), SCIPcreate(), SCIPcreateSol(), SCIPdebugMessage, SCIPendProbing(), SCIPfindConshdlr(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetCurrentNode(), SCIPgetLowerbound(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNConss(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetSols(), SCIPgetSolvingTime(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPinfinity(), SCIPisInfinity(), SCIPisParamFixed(), SCIPisStopped(), SCIPnodeGetNumber(), SCIPpresolve(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPstartProbing(), SCIPsumepsilon(), SCIPwarningMessage(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEURCOPY ( heurCopyVbounds  )

static

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

Definition at line 886 of file heur_vbounds.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurVbounds().

static SCIP_DECL_HEURFREE ( heurFreeVbounds  )

static

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

Definition at line 900 of file heur_vbounds.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), and SCIPheurSetData().

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

References heurdataReset(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArrayNull, SCIPheurGetData(), and SCIPreleaseVar().

static SCIP_DECL_HEUREXEC ( heurExecVbounds  )

static

execution method of primal heuristic

Definition at line 953 of file heur_vbounds.c.

References applyVbounds(), initializeCandsLists(), NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPgetNPseudoBranchCands(), and SCIPheurGetData().

SCIP_RETCODE SCIPincludeHeurVbounds

(

SCIP *

scip

)

creates the vbounds primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 996 of file heur_vbounds.c.

References DEFAULT_COPYCUTS, DEFAULT_MAXNODES, DEFAULT_MAXPROPROUNDS, DEFAULT_MINFIXINGRATE, DEFAULT_MINIMPROVE, DEFAULT_MINNODES, DEFAULT_NODESOFS, DEFAULT_NODESQUOT, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, heurdataReset(), NULL, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), and TRUE.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeDefaultPlugins().