Detailed Description

Large neighborhood search heuristic for Benders' decomposition based on trust region methods.

Author: Stephen J. Maher

The Trust Region heuristic draws upon trust region methods for solving optimization problems, especially in the context of Benders' decomposition. This heuristic has been developed to improve the heuristic performance of the Benders' decomposition algorithm within SCIP.

The Trust Region heuristic copies the original SCIP instance and adds a constraint to penalize changes from the incumbent solution. Consider a problem that includes a set of binary variables \(\mathcal{B}\). Given a feasible solution \(\hat{x}\) to the original problem, we define the set \(\mathcal{B}^{+}\) as the index set for the binary variables that are 1 in the input solution and \(\mathcal{B}^{-}\) as the index set for binary variables that are 0. The trust region constraint, which is added to the sub-SCIP, is given by

\[ \sum_{i \in \mathcal{B}^{+}}(1 - x_{i}) + \sum_{i \in \mathcal{B}^{-}}x_{i} \le \theta \]

The variable \(\theta\) measure the distance, in terms of the binary variables, of candidate solutions to the input solution.

In addition, an upper bounding constraint is explicitly added to enforce a minimum improvement from the heuristic, given by \(f(x) \le f(\hat{x}) - \epsilon\). The parameter \(\epsilon \ge 0\) denotes the minimum improvement that must be achieved by the heuristic.

The objective function is then modified to \(f(x) + M\theta\), where \(M\) is a parameter for penalizing the distance of solutions from the input solution \(\hat{x}\).

If a new incumbent solution is found by this heuristic, then the Trust Region heuristic is immediately re-executed with this new incumbent solution.

Definition in file heur_trustregion.c.

#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/heuristics.h"
#include "scip/heur_trustregion.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_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.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_var.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	HEUR_NAME "trustregion"

#define	HEUR_DESC "LNS heuristic for Benders' decomposition based on trust region methods"

#define	HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS

#define	HEUR_PRIORITY -1102010

#define	HEUR_FREQ -1

#define	HEUR_FREQOFS 0

#define	HEUR_MAXDEPTH -1

#define	HEUR_TIMING SCIP_HEURTIMING_AFTERNODE

#define	HEUR_USESSUBSCIP TRUE

#define	DEFAULT_MINBINVARS 10

#define	DEFAULT_NODESOFS 1000

#define	DEFAULT_MAXNODES 10000

#define	DEFAULT_MINNODES 100

#define	DEFAULT_NODESQUOT 0.05

#define	DEFAULT_LPLIMFAC 1.5

#define	DEFAULT_NWAITINGNODES 1

#define	DEFAULT_USELPROWS FALSE

#define	DEFAULT_COPYCUTS TRUE

#define	DEFAULT_BESTSOLLIMIT 3

#define	DEFAULT_VIOLPENALTY 100.0

#define	DEFAULT_OBJMINIMPROVE 1e-2

#define	EVENTHDLR_NAME "Trustregion"

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

#define	EXECUTE 0

#define	WAITFORNEWSOL 1

Functions
static SCIP_RETCODE	addTrustRegionConstraints (SCIP scip, SCIP subscip, SCIP_VAR *subvars, SCIP_HEURDATA heurdata)

static	SCIP_DECL_EVENTEXEC (eventExecTrustregion)

static	SCIP_DECL_HEURCOPY (heurCopyTrustregion)

static	SCIP_DECL_HEURFREE (heurFreeTrustregion)

static	SCIP_DECL_HEURINIT (heurInitTrustregion)

static SCIP_RETCODE	setupAndSolveSubscipTrustregion (SCIP scip, SCIP subscip, SCIP_HEUR heur, SCIP_Longint nsubnodes, SCIP_RESULT result)

static	SCIP_DECL_HEUREXEC (heurExecTrustregion)

SCIP_RETCODE	SCIPincludeHeurTrustregion (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "trustregion"

Definition at line 88 of file heur_trustregion.c.

◆ HEUR_DESC

#define HEUR_DESC "LNS heuristic for Benders' decomposition based on trust region methods"

Definition at line 89 of file heur_trustregion.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS

Definition at line 90 of file heur_trustregion.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -1102010

Definition at line 91 of file heur_trustregion.c.

◆ HEUR_FREQ

#define HEUR_FREQ -1

Definition at line 92 of file heur_trustregion.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 93 of file heur_trustregion.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 94 of file heur_trustregion.c.

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE

Definition at line 95 of file heur_trustregion.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 96 of file heur_trustregion.c.

◆ DEFAULT_MINBINVARS

#define DEFAULT_MINBINVARS 10

the minimum number of binary variables necessary to run the heuristic

Definition at line 98 of file heur_trustregion.c.

◆ DEFAULT_NODESOFS

#define DEFAULT_NODESOFS 1000

number of nodes added to the contingent of the total nodes

Definition at line 99 of file heur_trustregion.c.

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES 10000

maximum number of nodes to regard in the subproblem

Definition at line 100 of file heur_trustregion.c.

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES 100

minimum number of nodes required to start the subproblem

Definition at line 101 of file heur_trustregion.c.

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT 0.05

contingent of sub problem nodes in relation to original nodes

Definition at line 102 of file heur_trustregion.c.

◆ DEFAULT_LPLIMFAC

#define DEFAULT_LPLIMFAC 1.5

factor by which the limit on the number of LP depends on the node limit

Definition at line 103 of file heur_trustregion.c.

◆ DEFAULT_NWAITINGNODES

#define DEFAULT_NWAITINGNODES 1

number of nodes without incumbent change that heuristic should wait

Definition at line 104 of file heur_trustregion.c.

◆ DEFAULT_USELPROWS

#define DEFAULT_USELPROWS FALSE

should subproblem be created out of the rows in the LP rows, otherwise, the copy constructors of the constraints handlers are used

Definition at line 106 of file heur_trustregion.c.

◆ DEFAULT_COPYCUTS

#define DEFAULT_COPYCUTS TRUE

if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool of the original scip be copied to constraints of the subscip

Definition at line 108 of file heur_trustregion.c.

◆ DEFAULT_BESTSOLLIMIT

#define DEFAULT_BESTSOLLIMIT 3

limit on number of improving incumbent solutions in sub-CIP

Definition at line 109 of file heur_trustregion.c.

◆ DEFAULT_VIOLPENALTY

#define DEFAULT_VIOLPENALTY 100.0

the penalty for violating the trust region

Definition at line 111 of file heur_trustregion.c.

◆ DEFAULT_OBJMINIMPROVE

#define DEFAULT_OBJMINIMPROVE 1e-2

the minimum absolute improvement in the objective function value

Definition at line 112 of file heur_trustregion.c.

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "Trustregion"

Definition at line 115 of file heur_trustregion.c.

◆ EVENTHDLR_DESC

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

Definition at line 116 of file heur_trustregion.c.

◆ EXECUTE

#define EXECUTE 0

Definition at line 119 of file heur_trustregion.c.

◆ WAITFORNEWSOL

#define WAITFORNEWSOL 1

Definition at line 120 of file heur_trustregion.c.

Function Documentation

◆ addTrustRegionConstraints()

static SCIP_RETCODE addTrustRegionConstraints	(	SCIP *	scip,
		SCIP *	subscip,
		SCIP_VAR **	subvars,
		SCIP_HEURDATA *	heurdata
	)

static

create the extra constraint of trust region and add it to subscip

Parameters

scip	SCIP data structure of the original problem
subscip	SCIP data structure of the subproblem
subvars	variables of the subproblem
heurdata	heuristic's data structure

Definition at line 157 of file heur_trustregion.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPaddTrustregionNeighborhoodConstraint(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetProbName(), SCIPgetSolTransObj(), SCIPgetVarsData(), SCIPinfinity(), SCIPisObjIntegral(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetObj(), and TRUE.

Referenced by setupAndSolveSubscipTrustregion().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecTrustregion )

static

event handler execution callback to interrupt the solution process

Definition at line 233 of file heur_trustregion.c.

References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyTrustregion )

static

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

Definition at line 263 of file heur_trustregion.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeTrustregion )

static

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

Definition at line 277 of file heur_trustregion.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitTrustregion )

static

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

Definition at line 298 of file heur_trustregion.c.

References NULL, SCIP_OKAY, SCIPheurGetData(), and WAITFORNEWSOL.

◆ setupAndSolveSubscipTrustregion()

static SCIP_RETCODE setupAndSolveSubscipTrustregion	(	SCIP *	scip,
		SCIP *	subscip,
		SCIP_HEUR *	heur,
		SCIP_Longint	nsubnodes,
		SCIP_RESULT *	result
	)

static

sets up and solves the sub SCIP for the Trust Region heuristic

Parameters

scip	SCIP data structure
subscip	the subproblem created by trustregion
heur	trustregion heuristic
nsubnodes	nodelimit for subscip
result	result pointer

Definition at line 320 of file heur_trustregion.c.

References addTrustRegionConstraints(), EVENTHDLR_DESC, EVENTHDLR_NAME, EXECUTE, FALSE, HEUR_NAME, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DIDNOTRUN, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_STATUS_NODELIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcopyLargeNeighborhoodSearch(), SCIPdebug, SCIPdebugMsg, SCIPdropEvent(), SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetNNodes(), SCIPgetStatus(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPincludeEventhdlrBasic(), SCIPprintStatistics(), SCIPsetCommonSubscipParams(), SCIPsetIntParam(), SCIPsolve(), SCIPtransformProb(), SCIPtranslateSubSols(), and WAITFORNEWSOL.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecTrustregion )

static

execution method of primal heuristic

Definition at line 449 of file heur_trustregion.c.

References EXECUTE, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIPcheckCopyLimits(), SCIPcreate(), SCIPdebugMsg, SCIPfree(), SCIPgetBestSol(), SCIPgetNBinVars(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetSolNodenum(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNCalls(), SCIPheurGetNSolsFound(), SCIPisStopped(), SCIPsolGetHeur(), SCIPsolIsOriginal(), setupAndSolveSubscipTrustregion(), and WAITFORNEWSOL.

SCIP

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

◆ DEFAULT_MINBINVARS

◆ DEFAULT_NODESOFS

◆ DEFAULT_MAXNODES

◆ DEFAULT_MINNODES

◆ DEFAULT_NODESQUOT

◆ DEFAULT_LPLIMFAC

◆ DEFAULT_NWAITINGNODES

◆ DEFAULT_USELPROWS

◆ DEFAULT_COPYCUTS

◆ DEFAULT_BESTSOLLIMIT

◆ DEFAULT_VIOLPENALTY

◆ DEFAULT_OBJMINIMPROVE

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

◆ EXECUTE

◆ WAITFORNEWSOL

Function Documentation

◆ addTrustRegionConstraints()

◆ SCIP_DECL_EVENTEXEC()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ setupAndSolveSubscipTrustregion()

◆ SCIP_DECL_HEUREXEC()