Detailed Description

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

Author: Timo Berthold; Stefan Heinz; Jens Schulz

#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(), 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 94 of file heur_vbounds.c.

static SCIP_DECL_HASHKEYEQ ( hashKeyEqVar )

static

returns TRUE iff the indices of both variables are equal

Definition at line 101 of file heur_vbounds.c.

static SCIP_DECL_HASHKEYVAL ( hashKeyValVar )

static

returns the hash value of the key

Definition at line 110 of file heur_vbounds.c.

static void heurdataReset ( SCIP_HEURDATA * heurdata )

static

reset heuristic data structure

Parameters

heurdata structure containing heurdata

Definition at line 123 of file heur_vbounds.c.

References FALSE, and NULL.

Referenced by 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 140 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 163 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 254 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 369 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.

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 497 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 573 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 616 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.

static SCIP_DECL_HEURCOPY ( heurCopyVbounds )

static

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

Definition at line 891 of file heur_vbounds.c.

static SCIP_DECL_HEURFREE ( heurFreeVbounds )

static

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

Definition at line 905 of file heur_vbounds.c.

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

static SCIP_DECL_HEUREXEC ( heurExecVbounds )

static

execution method of primal heuristic

Definition at line 958 of file heur_vbounds.c.

SCIP_RETCODE SCIPincludeHeurVbounds ( SCIP * scip )

creates the vbounds primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1001 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 SCIPincludeDefaultPlugins().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation