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 "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/heuristics.h"
#include "scip/heur_proximity.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_event.h"
#include "scip/scip_exact.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_nlp.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_var.h"
#include <string.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 SCIP_HEURDISPCHAR_LNS
#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
#define	DEFAULT_MINIMPROVE 0.02
#define	DEFAULT_MINGAP 0.01
#define	DEFAULT_MINNODES 1LL
#define	DEFAULT_MINLPITERS 200LL
#define	DEFAULT_MAXLPITERS 100000LL
#define	DEFAULT_NODESOFS 50LL
#define	DEFAULT_WAITINGNODES 100LL
#define	DEFAULT_NODESQUOT 0.1
#define	DEFAULT_USELPROWS FALSE
#define	DEFAULT_BINVARQUOT 0.1
#define	DEFAULT_RESTART TRUE
#define	DEFAULT_USEFINALLP FALSE
#define	DEFAULT_LPITERSQUOT 0.2
#define	DEFAULT_USEUCT FALSE

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_HEURDATA heurdata, SCIP subscip)
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

◆ HEUR_NAME

#define HEUR_NAME "proximity"

Definition at line 67 of file heur_proximity.c.

◆ HEUR_DESC

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

Definition at line 68 of file heur_proximity.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS

Definition at line 69 of file heur_proximity.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -2000000

Definition at line 70 of file heur_proximity.c.

◆ HEUR_FREQ

#define HEUR_FREQ -1

Definition at line 71 of file heur_proximity.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 72 of file heur_proximity.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 73 of file heur_proximity.c.

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE

Definition at line 74 of file heur_proximity.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 75 of file heur_proximity.c.

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "Proximity"

Definition at line 78 of file heur_proximity.c.

◆ EVENTHDLR_DESC

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

Definition at line 79 of file heur_proximity.c.

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES 10000LL

maximum number of nodes to regard in the subproblem

Definition at line 83 of file heur_proximity.c.

◆ DEFAULT_MINIMPROVE

#define DEFAULT_MINIMPROVE 0.02

factor by which proximity should at least improve the incumbent

Definition at line 84 of file heur_proximity.c.

◆ DEFAULT_MINGAP

#define DEFAULT_MINGAP 0.01

minimum primal-dual gap for which the heuristic is executed

Definition at line 85 of file heur_proximity.c.

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES 1LL

minimum number of nodes to regard in the subproblem

Definition at line 86 of file heur_proximity.c.

◆ DEFAULT_MINLPITERS

#define DEFAULT_MINLPITERS 200LL

minimum number of LP iterations to perform in one sub-mip

Definition at line 87 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_MAXLPITERS

#define DEFAULT_MAXLPITERS 100000LL

maximum number of LP iterations to be performed in the subproblem

Definition at line 88 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity(), and SCIPincludeHeurZeroobj().

◆ DEFAULT_NODESOFS

#define DEFAULT_NODESOFS 50LL

number of nodes added to the contingent of the total nodes

Definition at line 89 of file heur_proximity.c.

◆ DEFAULT_WAITINGNODES

#define DEFAULT_WAITINGNODES 100LL

default waiting nodes since last incumbent before heuristic is executed

Definition at line 90 of file heur_proximity.c.

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT 0.1

default quotient of sub-MIP nodes with respect to number of processed nodes

Definition at line 91 of file heur_proximity.c.

◆ DEFAULT_USELPROWS

#define DEFAULT_USELPROWS FALSE

should subproblem be constructed based on LP row information?

Definition at line 92 of file heur_proximity.c.

◆ DEFAULT_BINVARQUOT

#define DEFAULT_BINVARQUOT 0.1

default threshold for percentage of binary variables required to start

Definition at line 93 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_RESTART

#define DEFAULT_RESTART TRUE

should the heuristic immediately run again on its newly found solution?

Definition at line 94 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_USEFINALLP

#define DEFAULT_USEFINALLP FALSE

should the heuristic solve a final LP in case of continuous objective variables?

Definition at line 95 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_LPITERSQUOT

#define DEFAULT_LPITERSQUOT 0.2

default quotient of sub-MIP LP iterations with respect to LP iterations so far

Definition at line 96 of file heur_proximity.c.

Referenced by SCIPincludeHeurProximity().

◆ DEFAULT_USEUCT

#define DEFAULT_USEUCT FALSE

should uct node selection be used at the beginning of the search?

Definition at line 97 of file heur_proximity.c.

Function Documentation

◆ solveLp()

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 142 of file heur_proximity.c.

References assert(), FALSE, lperror, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPchgVarLbDive(), SCIPchgVarUbDive(), SCIPdebugMsg, SCIPendDive(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPinDive(), SCIPisExact(), SCIPisNLPConstructed(), SCIPlinkLPSol(), SCIPsolveDiveLP(), SCIPstartDive(), SCIPtrySol(), SCIPunlinkSol(), SCIPvarGetLbGlobal(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), sol, TRUE, and vars.

Referenced by createNewSol().

◆ createNewSol()

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 239 of file heur_proximity.c.

References assert(), FALSE, i, MAX, MIN, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetObjNorm(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisLPConstructed(), SCIPisZero(), SCIPsetSolVal(), SCIPsetSolVals(), SCIPstatisticMessage, SCIPtrySol(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), solveLp(), TRUE, var, and vars.

Referenced by SCIPapplyProximity().

◆ setupSubproblem()

SCIP_RETCODE setupSubproblem	(	SCIP_HEURDATA *	heurdata,
		SCIP *	subscip )

static

sets solving parameters for the subproblem created by the heuristic

Parameters

heurdata	heuristic data structure
subscip	copied SCIP data structure

Definition at line 335 of file heur_proximity.c.

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

Referenced by SCIPapplyProximity().

◆ deleteSubproblem()

SCIP_RETCODE deleteSubproblem	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata )

static

frees the subproblem

Parameters

scip	SCIP data structure
heurdata	heuristic data

Definition at line 409 of file heur_proximity.c.

References assert(), heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPreleaseCons().

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

◆ SCIP_DECL_EVENTEXEC()

SCIP_DECL_EVENTEXEC ( eventExecProximity )

static

exec the event handler

We interrupt the solution process.

Definition at line 442 of file heur_proximity.c.

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

◆ SCIP_DECL_HEURCOPY()

SCIP_DECL_HEURCOPY ( heurCopyProximity )

static

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

Definition at line 470 of file heur_proximity.c.

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

◆ SCIP_DECL_HEURFREE()

SCIP_DECL_HEURFREE ( heurFreeProximity )

static

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

Definition at line 484 of file heur_proximity.c.

References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINIT()

SCIP_DECL_HEURINIT ( heurInitProximity )

static

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

Definition at line 505 of file heur_proximity.c.

References assert(), heurdata, NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXITSOL()

SCIP_DECL_HEUREXITSOL ( heurExitsolProximity )

static

solution process exiting method of proximity heuristic

Definition at line 534 of file heur_proximity.c.

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

◆ SCIP_DECL_HEUREXEC()

SCIP_DECL_HEUREXEC ( heurExecProximity )

static

execution method of primal heuristic

Definition at line 554 of file heur_proximity.c.

References assert(), deleteSubproblem(), FALSE, heurdata, MAX, MIN, nnodes, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPapplyProximity(), SCIPdebugMsg, SCIPdeleteSubproblemProximity(), SCIPgetNBinVars(), SCIPgetNNodes(), SCIPgetNObjVars(), SCIPgetNRootFirstLPIterations(), SCIPgetNVars(), SCIPheurGetData(), SCIPisStopped(), and TRUE.

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

◆ DEFAULT_MAXNODES

◆ DEFAULT_MINIMPROVE

◆ DEFAULT_MINGAP

◆ DEFAULT_MINNODES

◆ DEFAULT_MINLPITERS

◆ DEFAULT_MAXLPITERS

◆ DEFAULT_NODESOFS

◆ DEFAULT_WAITINGNODES

◆ DEFAULT_NODESQUOT

◆ DEFAULT_USELPROWS

◆ DEFAULT_BINVARQUOT

◆ DEFAULT_RESTART

◆ DEFAULT_USEFINALLP

◆ DEFAULT_LPITERSQUOT

◆ DEFAULT_USEUCT

Function Documentation

◆ solveLp()

◆ createNewSol()

◆ setupSubproblem()

◆ deleteSubproblem()

◆ SCIP_DECL_EVENTEXEC()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEUREXEC()