heur_proximity.c File Reference

Detailed Description

improvement heuristic which uses an auxiliary objective instead of the original objective function which is itself added as a constraint to a sub-SCIP instance. The heuristic was presented by Matteo Fischetti and Michele Monaci

Author

Gregor Hendel

Definition in file heur_proximity.c.

#include <assert.h>
#include <string.h>
#include "scip/heur_proximity.h"
#include "scip/cons_linear.h"

Go to the source code of this file.

Macros
#define	HEUR_NAME   "proximity"
#define	HEUR_DESC   "heuristic trying to improve the incumbent by an auxiliary proximity objective function"
#define	HEUR_DISPCHAR   'P'
#define	HEUR_PRIORITY   -2000000
#define	HEUR_FREQ   -1
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   -1
#define	HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE
#define	HEUR_USESSUBSCIP   TRUE
#define	EVENTHDLR_NAME   "Proximity"
#define	EVENTHDLR_DESC   "LP event handler for " HEUR_NAME " heuristic"
#define	DEFAULT_MAXNODES   10000LL /* maximum number of nodes to regard in the subproblem */
#define	DEFAULT_MINIMPROVE   0.02 /* factor by which proximity should at least improve the incumbent */
#define	DEFAULT_MINGAP   0.01 /* minimum primal-dual gap for which the heuristic is executed */
#define	DEFAULT_MINNODES   1LL /* minimum number of nodes to regard in the subproblem */
#define	DEFAULT_MINLPITERS   200LL /* minimum number of LP iterations to perform in one sub-mip */
#define	DEFAULT_MAXLPITERS   100000LL /* maximum number of LP iterations to be performed in the subproblem */
#define	DEFAULT_NODESOFS   50LL /* number of nodes added to the contingent of the total nodes */
#define	DEFAULT_WAITINGNODES   100LL /* default waiting nodes since last incumbent before heuristic is executed */
#define	DEFAULT_NODESQUOT   0.1 /* default quotient of sub-MIP nodes with respect to number of processed nodes*/
#define	DEFAULT_USELPROWS   FALSE /* should subproblem be constructed based on LP row information? */
#define	DEFAULT_BINVARQUOT   0.1 /* default threshold for percentage of binary variables required to start */
#define	DEFAULT_RESTART   TRUE /* should the heuristic immediately run again on its newly found solution? */
#define	DEFAULT_USEFINALLP   FALSE /* should the heuristic solve a final LP in case of continuous objective variables? */
#define	DEFAULT_LPITERSQUOT   0.2 /* default quotient of sub-MIP LP iterations with respect to LP iterations so far */

Functions
static SCIP_RETCODE	solveLp (SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
static SCIP_RETCODE	createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool usefinallp, SCIP_Bool *success)
static SCIP_RETCODE	setupSubproblem (SCIP *subscip)
static SCIP_RETCODE	createRows (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars)
static SCIP_RETCODE	deleteSubproblem (SCIP *scip, SCIP_HEURDATA *heurdata)
static	SCIP_DECL_EVENTEXEC (eventExecProximity)
static	SCIP_DECL_HEURCOPY (heurCopyProximity)
static	SCIP_DECL_HEURFREE (heurFreeProximity)
static	SCIP_DECL_HEURINIT (heurInitProximity)
static	SCIP_DECL_HEUREXITSOL (heurExitsolProximity)
static	SCIP_DECL_HEUREXEC (heurExecProximity)
SCIP_RETCODE	SCIPdeleteSubproblemProximity (SCIP *scip)
SCIP_RETCODE	SCIPapplyProximity (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes, SCIP_Longint nlpiters, SCIP_Longint *nusednodes, SCIP_Longint *nusedlpiters, SCIP_Bool freesubscip)
SCIP_RETCODE	SCIPincludeHeurProximity (SCIP *scip)

Macro Definition Documentation

#define HEUR_NAME   "proximity"

Definition at line 33 of file heur_proximity.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIPapplyProximity(), SCIPdeleteSubproblemProximity(), and SCIPincludeHeurProximity().

#define HEUR_DESC   "heuristic trying to improve the incumbent by an auxiliary proximity objective function"

Definition at line 34 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define HEUR_DISPCHAR   'P'

Definition at line 35 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define HEUR_PRIORITY   -2000000

Definition at line 36 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define HEUR_FREQ   -1

Definition at line 37 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define HEUR_FREQOFS   0

Definition at line 38 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define HEUR_MAXDEPTH   -1

Definition at line 39 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 40 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 41 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define EVENTHDLR_NAME   "Proximity"

Definition at line 44 of file heur_proximity.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPapplyProximity().

#define EVENTHDLR_DESC   "LP event handler for " HEUR_NAME " heuristic"

Definition at line 45 of file heur_proximity.c.

Referenced by SCIPapplyProximity().

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

Definition at line 49 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_MINIMPROVE   0.02 /* factor by which proximity should at least improve the incumbent */

Definition at line 50 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_MINGAP   0.01 /* minimum primal-dual gap for which the heuristic is executed */

Definition at line 51 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

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

Definition at line 52 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_MINLPITERS   200LL /* minimum number of LP iterations to perform in one sub-mip */

Definition at line 53 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_MAXLPITERS   100000LL /* maximum number of LP iterations to be performed in the subproblem */

Definition at line 54 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

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

Definition at line 55 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_WAITINGNODES   100LL /* default waiting nodes since last incumbent before heuristic is executed */

Definition at line 56 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_NODESQUOT   0.1 /* default quotient of sub-MIP nodes with respect to number of processed nodes*/

Definition at line 57 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_USELPROWS   FALSE /* should subproblem be constructed based on LP row information? */

Definition at line 58 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_BINVARQUOT   0.1 /* default threshold for percentage of binary variables required to start */

Definition at line 59 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_RESTART   TRUE /* should the heuristic immediately run again on its newly found solution? */

Definition at line 60 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_USEFINALLP   FALSE /* should the heuristic solve a final LP in case of continuous objective variables? */

Definition at line 61 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

#define DEFAULT_LPITERSQUOT   0.2 /* default quotient of sub-MIP LP iterations with respect to LP iterations so far */

Definition at line 62 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

Function Documentation

static SCIP_RETCODE solveLp ( SCIP *  scip, SCIP_SOL *  sol, SCIP_Bool *  success  )

static

optimizes the continuous variables in an LP diving by fixing all integer variables to the given solution values

Parameters

scip	SCIP data structure
sol	candidate solution for which continuous variables should be optimized
success	was the dive successful?

Definition at line 106 of file heur_proximity.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPchgVarLbDive(), SCIPchgVarUbDive(), SCIPdebugMessage, SCIPendDive(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisNLPConstructed(), SCIPlinkLPSol(), SCIPsolveDiveLP(), SCIPstartDive(), SCIPtrySol(), SCIPvarGetLbGlobal(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), and TRUE.

Referenced by createNewSol().

static SCIP_RETCODE createNewSol ( SCIP *  scip, SCIP *  subscip, SCIP_VAR **  subvars, SCIP_HEUR *  heur, SCIP_SOL *  subsol, SCIP_Bool  usefinallp, 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
heur	proximity heuristic structure
subsol	solution of the subproblem
usefinallp	should continuous variables be optimized by a final LP
success	used to store whether new solution was found or not

Definition at line 191 of file heur_proximity.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetNOrigVars(), SCIPgetObjNorm(), SCIPgetSolOrigObj(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPisLPConstructed(), SCIPisZero(), SCIPsetSolVal(), SCIPsetSolVals(), SCIPstatisticMessage, SCIPtrySol(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarIsIntegral(), solveLp(), and TRUE.

Referenced by SCIPapplyProximity().

static SCIP_RETCODE setupSubproblem ( SCIP *  subscip )

static

sets solving parameters for the subproblem created by the heuristic

Parameters

subscip

copied SCIP data structure

Definition at line 286 of file heur_proximity.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfindNodesel(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), and TRUE.

Referenced by SCIPapplyProximity().

static SCIP_RETCODE createRows ( SCIP *  scip, SCIP *  subscip, SCIP_VAR **  subvars  )

static

creates the rows of the subproblem

Parameters

scip	original SCIP data structure
subscip	SCIP data structure for the subproblem
subvars	the variables of the subproblem

Definition at line 364 of file heur_proximity.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPcolGetVar(), SCIPcreateConsLinear(), SCIPfreeBufferArray, SCIPgetLPRowsData(), SCIPreleaseCons(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsLocal(), SCIPvarGetProbindex(), and TRUE.

Referenced by SCIPapplyProximity().

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

static

frees the subproblem

Parameters

scip	SCIP data structure
heurdata	heuristic data

Definition at line 425 of file heur_proximity.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPreleaseCons().

Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXITSOL(), SCIPapplyProximity(), and SCIPdeleteSubproblemProximity().

static SCIP_DECL_EVENTEXEC ( eventExecProximity  )

static

Definition at line 459 of file heur_proximity.c.

References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODESOLVED, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_OKAY, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), and SCIPinterruptSolve().

static SCIP_DECL_HEURCOPY ( heurCopyProximity  )

static

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

Definition at line 485 of file heur_proximity.c.

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

static SCIP_DECL_HEURFREE ( heurFreeProximity  )

static

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

Definition at line 499 of file heur_proximity.c.

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

static SCIP_DECL_HEURINIT ( heurInitProximity  )

static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 520 of file heur_proximity.c.

References NULL, SCIP_OKAY, and SCIPheurGetData().

static SCIP_DECL_HEUREXITSOL ( heurExitsolProximity  )

static

Definition at line 549 of file heur_proximity.c.

References deleteSubproblem(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPheurGetData().

static SCIP_DECL_HEUREXEC ( heurExecProximity  )

static

execution method of primal heuristic

Definition at line 570 of file heur_proximity.c.

References deleteSubproblem(), FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIPapplyProximity(), SCIPdebugMessage, SCIPdeleteSubproblemProximity(), SCIPgetNBinVars(), SCIPgetNNodes(), SCIPgetNObjVars(), SCIPgetNRootFirstLPIterations(), SCIPgetNVars(), SCIPheurGetData(), SCIPisStopped(), and TRUE.

SCIP_RETCODE SCIPdeleteSubproblemProximity

(

SCIP *

scip

)

frees the sub-MIP created by proximity

Parameters

scip	SCIP data structure

Definition at line 674 of file heur_proximity.c.

References deleteSubproblem(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPfindHeur(), and SCIPheurGetData().

Referenced by SCIP_DECL_HEUREXEC().

SCIP_RETCODE SCIPapplyProximity	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_RESULT *	result,
		SCIP_Real	minimprove,
		SCIP_Longint	nnodes,
		SCIP_Longint	nlpiters,
		SCIP_Longint *	nusednodes,
		SCIP_Longint *	nusedlpiters,
		SCIP_Bool	freesubscip
	)

main procedure of the proximity heuristic, creates and solves a sub-SCIP

Note

the method can be applied in an iterative way, keeping the same subscip in between. If the freesubscip parameter is set to FALSE, the heuristic will keep the subscip data structures. Always set this parameter to TRUE, or call SCIPdeleteSubproblemProximity() afterwards

Parameters

scip	original SCIP data structure
heur	heuristic data structure
result	result data structure
minimprove	factor by which proximity should at least improve the incumbent
nnodes	node limit for the subproblem
nlpiters	LP iteration limit for the subproblem
nusednodes	pointer to store number of used nodes in subscip
nusedlpiters	pointer to store number of used LP iterations in subscip
freesubscip	should the created sub-MIP be freed at the end of the method?

Definition at line 701 of file heur_proximity.c.

References createNewSol(), createRows(), deleteSubproblem(), EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_EVENTTYPE_NODESOLVED, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPcatchEvent(), SCIPchgRhsLinear(), SCIPchgVarLbGlobal(), SCIPchgVarObj(), SCIPchgVarUbGlobal(), SCIPcopy(), SCIPcopyPlugins(), SCIPcopyVars(), SCIPcreate(), SCIPcreateConsBasicLinear(), SCIPcreateProbBasic(), SCIPdebug, SCIPdebugMessage, SCIPdropEvent(), SCIPerrorMessage, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfeastol(), SCIPfindEventhdlr(), SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetGap(), SCIPgetLowerbound(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNBinVars(), SCIPgetNFixedVars(), SCIPgetNLPIterations(), SCIPgetNNodes(), SCIPgetNRootLPIterations(), SCIPgetNSols(), SCIPgetNSolsFound(), SCIPgetPresolvingTime(), SCIPgetPrimalbound(), SCIPgetRealParam(), SCIPgetRhsLinear(), SCIPgetSolTransObj(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPheurGetName(), SCIPincludeEventhdlrBasic(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisObjIntegral(), SCIPpresolve(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsolGetHeur(), SCIPsolGetIndex(), SCIPsolGetNodenum(), SCIPsolIsOriginal(), SCIPsolve(), SCIPstatisticMessage, SCIPtransformProb(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPwarningMessage(), setupSubproblem(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

SCIP_RETCODE SCIPincludeHeurProximity

(

SCIP *

scip

)

creates the proximity primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1081 of file heur_proximity.c.

References DEFAULT_BINVARQUOT, DEFAULT_LPITERSQUOT, DEFAULT_MAXLPITERS, DEFAULT_MAXNODES, DEFAULT_MINGAP, DEFAULT_MINIMPROVE, DEFAULT_MINLPITERS, DEFAULT_MINNODES, DEFAULT_NODESOFS, DEFAULT_NODESQUOT, DEFAULT_RESTART, DEFAULT_USEFINALLP, DEFAULT_USELPROWS, DEFAULT_WAITINGNODES, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPinfinity(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInit(), and TRUE.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeDefaultPlugins().