Detailed Description
Large neighborhood search heuristic for Benders' decomposition based on trust region methods.
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.
Referenced by SCIPincludeHeurTrustregion(), and setupAndSolveSubscipTrustregion().
◆ HEUR_DESC
#define HEUR_DESC "LNS heuristic for Benders' decomposition based on trust region methods" |
Definition at line 89 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 90 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -1102010 |
Definition at line 91 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ HEUR_FREQ
#define HEUR_FREQ -1 |
Definition at line 92 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 93 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 94 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 95 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 96 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ 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.
Referenced by SCIPincludeHeurTrustregion().
◆ 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.
Referenced by SCIPincludeHeurTrustregion().
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 10000 |
maximum number of nodes to regard in the subproblem
Definition at line 100 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 100 |
minimum number of nodes required to start the subproblem
Definition at line 101 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ 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.
Referenced by SCIPincludeHeurTrustregion().
◆ 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.
Referenced by SCIPincludeHeurTrustregion().
◆ 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.
Referenced by SCIPincludeHeurTrustregion().
◆ 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 105 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ 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.
Referenced by SCIPincludeHeurTrustregion().
◆ DEFAULT_BESTSOLLIMIT
#define DEFAULT_BESTSOLLIMIT 3 |
limit on number of improving incumbent solutions in sub-CIP
Definition at line 111 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ DEFAULT_VIOLPENALTY
#define DEFAULT_VIOLPENALTY 100.0 |
the penalty for violating the trust region
Definition at line 113 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ DEFAULT_OBJMINIMPROVE
#define DEFAULT_OBJMINIMPROVE 1e-2 |
the minimum absolute improvement in the objective function value
Definition at line 114 of file heur_trustregion.c.
Referenced by SCIPincludeHeurTrustregion().
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "Trustregion" |
Definition at line 117 of file heur_trustregion.c.
Referenced by setupAndSolveSubscipTrustregion().
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 118 of file heur_trustregion.c.
Referenced by setupAndSolveSubscipTrustregion().
◆ EXECUTE
#define EXECUTE 0 |
Definition at line 121 of file heur_trustregion.c.
Referenced by setupAndSolveSubscipTrustregion().
◆ WAITFORNEWSOL
#define WAITFORNEWSOL 1 |
Definition at line 122 of file heur_trustregion.c.
Referenced by setupAndSolveSubscipTrustregion().
Function Documentation
◆ addTrustRegionConstraints()
|
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 159 of file heur_trustregion.c.
References FALSE, NULL, SCIP_CALL, SCIP_DECL_EVENTEXEC(), 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 |
event handler execution callback to interrupt the solution process
Definition at line 235 of file heur_trustregion.c.
Referenced by addTrustRegionConstraints().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 265 of file heur_trustregion.c.
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 279 of file heur_trustregion.c.
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 300 of file heur_trustregion.c.
◆ setupAndSolveSubscipTrustregion()
|
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 322 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_DECL_HEUREXEC(), SCIP_DIDNOTRUN, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, 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.
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 451 of file heur_trustregion.c.
Referenced by setupAndSolveSubscipTrustregion().