Scippy

SCIP

Solving Constraint Integer Programs

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"

◆ 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 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
scipSCIP data structure of the original problem
subscipSCIP data structure of the subproblem
subvarsvariables of the subproblem
heurdataheuristic'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 SCIP_DECL_EVENTEXEC ( eventExecTrustregion  )
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 SCIP_DECL_HEURCOPY ( heurCopyTrustregion  )
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 SCIP_DECL_HEURFREE ( heurFreeTrustregion  )
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 SCIP_DECL_HEURINIT ( heurInitTrustregion  )
static

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

Definition at line 300 of file heur_trustregion.c.

◆ setupAndSolveSubscipTrustregion()

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecTrustregion  )
static

execution method of primal heuristic

Definition at line 451 of file heur_trustregion.c.

Referenced by setupAndSolveSubscipTrustregion().