# SCIP

Solving Constraint Integer Programs

sepa_lagromory.c File Reference

## Detailed Description

Lagromory separator.

This separator is based on the following article that discusses Lagromory separation using the relax-and-cut framework. Multiple enhancements have been implemented on top of the basic algorithm described in the article.

Fischetti M. and Salvagnin D. (2011).
A relax-and-cut framework for Gomory mixed-integer cuts.
Mathematical Programming Computation, 3, 79-102.

Consider the following linear relaxation at a node:

$\begin{array}{rrl} \min & c^T x &\\ & x & \in P, \end{array}$

where $$P$$ is the feasible region of the relaxation. Let the following be the cuts generated so far in the current separation round.

${\alpha^i}^T x \leq \alpha^i_0, i = 1, 2, \hdots, M$

Then, the following is the Lagrangian dual problem considered in the relax-and-cut framework used in the separator.

$z_D := \max\limits_{u \geq 0} \left\{L(u) := \min \left\{c^T x + \sum\limits_{i = 1}^{M} \left(u_i \left({\alpha^i}^T x - \alpha^i_0\right) \right) \mid x \in P\right\} \right\},$

where $$u$$ are the Lagrangian multipliers (referred to as dualvector in this separator) used for penalizing the violation of the generated cuts, and $$z_D$$ is the optimal objective value (which is approximated via ubparam in this separator). Then, the following are the steps of the relax-and-cut algorithm implemented in this separator.

{itemize} Generate an initial pool of cuts to build the initial Lagrangian dual problem. Select initial values for Lagrangian multipliers $$u^0$$ (e.g., all zeroes vector). In the outer main loop $$i$$ of the algorithm: {enumerate} Solve the Lagrangian dual problem until certain termination criterion is met. This results in an inner subgradient loop, whose iteration $$j$$ is described below. {enumerate} Fix $$u^j$$, and solve the LP corresponding to the Lagrangian dual with fixed multipliers. Gather its optimal simplex tableau and optimal objective value (i.e., the Lagrangian value) $$L(u^j)$$. Update $$u^j$$ to $$u^{j+1}$$ as follows.

$u^{j+1} = \left(u^j + \lambda_j s^k\right)_+,$

where $$\lambda_j$$ is the step length:

$\lambda_j = \frac{\mu_j (UB - L(u^j))}{\|s^j\|^2_2},$

where $$mu_j$$ is a factor (i.e., muparam) such that $$0 < \mu_j \leq 2$$, UB is ubparam, and $$s^j$$ is the subgradient vector defined as:

$s^j_k = \left({\alpha^k}^T x - \alpha^k_0\right), k = 1, 2, \hdots, M.$

The factor $$mu_j$$ is updated as below.

$mu_j = \begin{cases} \p mubacktrackfactor * mu_j & \text{if } L(u^j) < bestLB - \delta\\ \begin{cases} \p muslab1factor * mu_j & \text{if } bestLB - avgLB < \p deltaslab1ub * delta\\ \p muslab2factor * mu_j & \text{if } \p deltaslab1ub * \delta \leq bestLB - avgLB < \p deltaslab2ub * delta\\ \p muslab3factor * mu_j & \text{otherwise} \end{cases} & \text{otherwise}, \end{cases}$

where $$bestLB$$ and $$avgLB$$ are best and average Lagrangian values found so far, and $$\delta = UB - bestLB$$. Stabilize $$u^{j+1}$$ by projecting onto a norm ball followed by taking a convex combination with a core vector of Lagrangian multipliers. Generate GMI cuts based on the optimal simplex tableau. Relax the newly generated cuts by penalizing and adding them to the objective function. Go to the next iteration $$j+1$$. {enumerate} Gather all the generated cuts and build an LP by adding all these cuts to the node relaxation. Solve this LP to obtain its optimal primal and dual solutions. If this primal solution is MIP primal feasible, then add this solution to the solution pool, add all the generated cuts to the cutpool or sepastore as needed, and exit the separator. Otherwise, update the Lagrangian multipliers based on this optimal dual solution, and go to the next iteration $$i+1$$. {enumerate} {itemize}

Definition in file sepa_lagromory.c.

#include "scip/heur_trysol.h"
#include "scip/sepa_lagromory.h"

Go to the source code of this file.

## Macros

#define SEPA_NAME   "lagromory"

#define SEPA_DESC   "separator for Lagromory cuts for MIP relaxations"

#define SEPA_PRIORITY   -8000

#define SEPA_FREQ   -1

#define SEPA_MAXBOUNDDIST   1.0

#define SEPA_USESSUBSCIP   FALSE

#define SEPA_DELAY   FALSE

#define DEFAULT_AWAY   0.01

#define DEFAULT_DELAYEDCUTS   FALSE

#define DEFAULT_SEPARATEROWS   TRUE

#define DEFAULT_SORTCUTOFFSOL   TRUE

#define DEFAULT_SIDETYPEBASIS   TRUE

#define DEFAULT_DYNAMICCUTS   TRUE

#define DEFAULT_MAKEINTEGRAL   FALSE

#define DEFAULT_FORCECUTS   FALSE

#define DEFAULT_ALLOWLOCAL   FALSE

#define DEFAULT_MAXROUNDSROOT   1

#define DEFAULT_MAXROUNDS   1

#define DEFAULT_DUALDEGENERACYRATETHRESHOLD   0.5

#define DEFAULT_VARCONSRATIOTHRESHOLD   1.0

#define DEFAULT_MINRESTART   1

#define DEFAULT_PERLPMAXCUTSROOT   50

#define DEFAULT_PERLPMAXCUTS   10

#define DEFAULT_PERROUNDLPITERLIMITFACTOR   -1.0

#define DEFAULT_ROOTLPITERLIMITFACTOR   -1.0

#define DEFAULT_TOTALLPITERLIMITFACTOR   -1.0

#define DEFAULT_PERROUNDMAXLPITERS   50000

#define DEFAULT_PERROUNDCUTSFACTORROOT   1.0

#define DEFAULT_PERROUNDCUTSFACTOR   0.5

#define DEFAULT_TOTALCUTSFACTOR   50.0

#define DEFAULT_MAXMAINITERS   4

#define DEFAULT_MAXSUBGRADIENTITERS   6

#define DEFAULT_MUPARAMCONST   TRUE

#define DEFAULT_MUPARAMINIT   0.01

#define DEFAULT_MUPARAMLB   0.0

#define DEFAULT_MUPARAMUB   2.0

#define DEFAULT_MUBACKTRACKFACTOR   0.5

#define DEFAULT_MUSLAB1FACTOR   10.0

#define DEFAULT_MUSLAB2FACTOR   2.0

#define DEFAULT_MUSLAB3FACTOR   0.5

#define DEFAULT_DELTASLAB1UB   0.001

#define DEFAULT_DELTASLAB2UB   0.01

#define DEFAULT_UBPARAMPOSFACTOR   2.0

#define DEFAULT_UBPARAMNEGFACTOR   0.5

#define DEFAULT_MAXLAGRANGIANVALSFORAVG   2

#define DEFAULT_MAXCONSECITERSFORMUUPDATE   10

#define DEFAULT_PERROOTLPITERFACTOR   0.2

#define DEFAULT_PERLPITERFACTOR   0.1

#define DEFAULT_CUTGENFREQ   1

#define DEFAULT_CUTADDFREQ   1

#define DEFAULT_CUTSFILTERFACTOR   1.0

#define DEFAULT_OPTIMALFACEPRIORITY   2

#define DEFAULT_AGGREGATECUTS   TRUE

#define DEFAULT_PROJECTIONTYPE   2

#define DEFAULT_STABILITYCENTERTYPE   1

#define DEFAULT_RADIUSINIT   0.5

#define DEFAULT_RADIUSMAX   20.0

#define DEFAULT_RADIUSMIN   1e-6

#define DEFAULT_CONST   2.0

#define DEFAULT_RADIUSUPDATEWEIGHT   0.98

#define RANDSEED   42

#define MAKECONTINTEGRAL   FALSE

#define POSTPROCESS   TRUE

#define BOUNDSWITCH   0.9999

#define USEVBDS   TRUE

#define FIXINTEGRALRHS   FALSE

#define MAXAGGRLEN(ncols)   (0.1*(ncols)+1000)

## Functions

static SCIP_RETCODE createLPWithSoftCuts (SCIP *scip, SCIP_SEPADATA *sepadata)

static SCIP_RETCODE deleteLPWithSoftCuts (SCIP *scip, SCIP_SEPADATA *sepadata)

static SCIP_RETCODE createLPWithHardCuts (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW **cuts, int ncuts)

static SCIP_RETCODE sepadataFree (SCIP *scip, SCIP_SEPADATA **sepadata)

static SCIP_RETCODE updateMuSteplengthParam (SCIP *scip, SCIP_SEPADATA *sepadata, int subgradientiternum, SCIP_Real ubparam, SCIP_Real *lagrangianvals, SCIP_Real bestlagrangianval, SCIP_Real avglagrangianval, SCIP_Real *muparam, SCIP_Bool *backtrack)

static void updateSubgradient (SCIP *scip, SCIP_SOL *sol, SCIP_ROW **cuts, int ncuts, SCIP_Real *subgradient, SCIP_Real *dualvector, SCIP_Bool *subgradientzero, int *ncutviols, SCIP_Real *maxcutviol, int *nnzsubgradientdualprod, SCIP_Real *maxnzsubgradientdualprod)

static void updateLagrangianValue (SCIP *scip, SCIP_Real objval, SCIP_Real *dualvector, SCIP_ROW **cuts, int ncuts, SCIP_Real *lagrangianval)

static void updateStepLength (SCIP *scip, SCIP_Real muparam, SCIP_Real ubparam, SCIP_Real lagrangianval, SCIP_Real *subgradient, int ncuts, SCIP_Real *steplength)

static void updateBallRadius (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Real *ballradius)

static SCIP_RETCODE l1BallProjection (SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)

static void l2BallProjection (SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)

static void linfBallProjection (SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)

static void weightedDualVector (SCIP_SEPADATA *sepadata, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real *stabilitycenter, int stabilitycenterlen, int nbestdualupdates, int totaliternum)

static SCIP_RETCODE stabilizeDualVector (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real *bestdualvector, int bestdualvectorlen, int nbestdualupdates, int subgradientiternum, int totaliternum, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Real *ballradius)

static SCIP_RETCODE updateDualVector (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *dualvector1, SCIP_Real *dualvector2, int dualvector2len, int ndualvector2updates, int subgradientiternum, int totaliternum, SCIP_Real steplength, SCIP_Real *subgradient, int ncuts, SCIP_Bool backtrack, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Bool *dualvecsdiffer, SCIP_Real *ballradius)

static SCIP_RETCODE checkLagrangianDualTermination (SCIP_SEPADATA *sepadata, int nnewaddedsoftcuts, int nyettoaddsoftcuts, SCIP_Bool objvecsdiffer, int ngeneratedcurrroundcuts, int nmaxgeneratedperroundcuts, int ncurrroundlpiters, int depth, SCIP_Bool *terminate)

static SCIP_RETCODE solveLagromoryLP (SCIP *scip, SCIP_SEPADATA *sepadata, int depth, SCIP_Real origobjoffset, SCIP_Bool *solfound, SCIP_SOL *sol, SCIP_Real *solvals, SCIP_Real *objval, int *ncurrroundlpiters)

static SCIP_RETCODE solveLPWithHardCuts (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Bool *solfound, SCIP_SOL *sol, SCIP_Real *solvals)

static SCIP_RETCODE constructCutRow (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int mainiternum, int subgradientiternum, int cutnnz, int *cutinds, SCIP_Real *cutcoefs, SCIP_Real cutefficacy, SCIP_Real cutrhs, SCIP_Bool cutislocal, int cutrank, SCIP_ROW **generatedcuts, SCIP_Real *generatedcutefficacies, int ngeneratedcurrroundcuts, int *ngeneratednewcuts, SCIP_Bool *cutoff)

static SCIP_RETCODE aggregateGeneratedCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_ROW **generatedcuts, SCIP_Real *bestdualvector, int bestdualvectorlen, SCIP_ROW **aggrcuts, int *naggrcuts, SCIP_Bool *cutoff)

static SCIP_RETCODE generateGMICuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int mainiternum, int subgradientiternum, SCIP_SOL *sol, SCIP_Real *solvals, int nmaxgeneratedperroundcuts, SCIP_Bool allowlocal, SCIP_ROW **generatedcurrroundcuts, SCIP_Real *generatedcutefficacies, int ngeneratedcurrroundcuts, int *ngeneratednewcuts, int depth, SCIP_Bool *cutoff)

static SCIP_RETCODE updateObjectiveVector (SCIP *scip, SCIP_Real *dualvector, SCIP_ROW **cuts, int ncuts, SCIP_Real *origobjcoefs, SCIP_Bool *objvecsdiffer)

static SCIP_RETCODE addGMICutsAsSoftConss (SCIP_Real *dualvector, int ngeneratedcuts, int *naddedcuts, int *nnewaddedsoftcuts)

static SCIP_RETCODE solveLagrangianDual (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *solvals, int mainiternum, SCIP_Real ubparam, int depth, SCIP_Bool allowlocal, int nmaxgeneratedperroundcuts, SCIP_Real *origobjcoefs, SCIP_Real origobjoffset, SCIP_Real *dualvector, int *nsoftcuts, SCIP_ROW **generatedcurrroundcuts, SCIP_Real *generatedcutefficacies, int *ngeneratedcutsperiter, int *ngeneratedcurrroundcuts, int *ncurrroundlpiters, SCIP_Bool *cutoff, SCIP_Real *bestlagrangianval, SCIP_Real *bestdualvector, int *bestdualvectorlen, int *nbestdualupdates, int *totaliternum)

static SCIP_RETCODE generateInitCutPool (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int mainiternum, SCIP_SOL *sol, SCIP_Real *solvals, int nmaxgeneratedperroundcuts, SCIP_Bool allowlocal, SCIP_ROW **generatedcurrroundcuts, SCIP_Real *generatedcutefficacies, int *ngeneratedcutsperiter, int *ngeneratedcurrroundcuts, int depth, SCIP_Bool *cutoff)

static SCIP_RETCODE addCuts (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW **cuts, int ncuts, SCIP_Longint maxdnom, SCIP_Real maxscale, int *naddedcuts, SCIP_Bool *cutoff)

static SCIP_RETCODE checkMainLoopTermination (SCIP_SEPADATA *sepadata, SCIP_Bool cutoff, SCIP_Bool dualvecsdiffer, int ngeneratedcurrroundcuts, int nsoftcuts, int nmaxgeneratedperroundcuts, int ncurrroundlpiters, int depth, SCIP_Bool *terminate)

static SCIP_RETCODE separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_Real ubparam, int depth, SCIP_Bool allowlocal, SCIP_RESULT *result)

static SCIP_RETCODE sepadataCreate (SCIP *scip, SCIP_SEPADATA **sepadata)

static SCIP_DECL_SEPACOPY (sepaCopyLagromory)

static SCIP_DECL_SEPAFREE (sepaFreeLagromory)

static SCIP_DECL_SEPAINIT (sepaInitLagromory)

static SCIP_DECL_SEPAEXIT (sepaExitLagromory)

static SCIP_DECL_SEPAEXECLP (sepaExeclpLagromory)

SCIP_RETCODE SCIPincludeSepaLagromory (SCIP *scip)

## ◆ SEPA_NAME

 #define SEPA_NAME   "lagromory"

Definition at line 144 of file sepa_lagromory.c.

Referenced by sepadataCreate().

## ◆ SEPA_DESC

 #define SEPA_DESC   "separator for Lagromory cuts for MIP relaxations"

Definition at line 145 of file sepa_lagromory.c.

## ◆ SEPA_PRIORITY

 #define SEPA_PRIORITY   -8000

Definition at line 146 of file sepa_lagromory.c.

## ◆ SEPA_FREQ

 #define SEPA_FREQ   -1

Definition at line 147 of file sepa_lagromory.c.

## ◆ SEPA_MAXBOUNDDIST

 #define SEPA_MAXBOUNDDIST   1.0

Definition at line 148 of file sepa_lagromory.c.

## ◆ SEPA_USESSUBSCIP

 #define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 149 of file sepa_lagromory.c.

## ◆ SEPA_DELAY

 #define SEPA_DELAY   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 150 of file sepa_lagromory.c.

## ◆ DEFAULT_AWAY

 #define DEFAULT_AWAY   0.01

minimal integrality violation of a basis variable to try separation

Definition at line 153 of file sepa_lagromory.c.

## ◆ DEFAULT_DELAYEDCUTS

 #define DEFAULT_DELAYEDCUTS   FALSE

should cuts be added to the delayed cut pool?

Definition at line 154 of file sepa_lagromory.c.

## ◆ DEFAULT_SEPARATEROWS

 #define DEFAULT_SEPARATEROWS   TRUE

separate rows with integral slack?

Definition at line 155 of file sepa_lagromory.c.

## ◆ DEFAULT_SORTCUTOFFSOL

 #define DEFAULT_SORTCUTOFFSOL   TRUE

sort fractional integer columns based on fractionality?

Definition at line 156 of file sepa_lagromory.c.

## ◆ DEFAULT_SIDETYPEBASIS

 #define DEFAULT_SIDETYPEBASIS   TRUE

choose side types of row (lhs/rhs) based on basis information?

Definition at line 157 of file sepa_lagromory.c.

## ◆ DEFAULT_DYNAMICCUTS

 #define DEFAULT_DYNAMICCUTS   TRUE

should generated cuts be removed from the LP if they are no longer tight?

Definition at line 158 of file sepa_lagromory.c.

## ◆ DEFAULT_MAKEINTEGRAL

 #define DEFAULT_MAKEINTEGRAL   FALSE

try to scale all cuts to integral coefficients?

Definition at line 159 of file sepa_lagromory.c.

## ◆ DEFAULT_FORCECUTS

 #define DEFAULT_FORCECUTS   FALSE

force cuts to be added to the LP?

Definition at line 160 of file sepa_lagromory.c.

## ◆ DEFAULT_ALLOWLOCAL

 #define DEFAULT_ALLOWLOCAL   FALSE

should locally valid cuts be generated?

Definition at line 161 of file sepa_lagromory.c.

## ◆ DEFAULT_MAXROUNDSROOT

 #define DEFAULT_MAXROUNDSROOT   1

maximal number of separation rounds in the root node (-1: unlimited)

Definition at line 164 of file sepa_lagromory.c.

## ◆ DEFAULT_MAXROUNDS

 #define DEFAULT_MAXROUNDS   1

maximal number of separation rounds per node (-1: unlimited)

Definition at line 165 of file sepa_lagromory.c.

## ◆ DEFAULT_DUALDEGENERACYRATETHRESHOLD

 #define DEFAULT_DUALDEGENERACYRATETHRESHOLD   0.5

minimum dual degeneracy rate for separator execution

Definition at line 166 of file sepa_lagromory.c.

## ◆ DEFAULT_VARCONSRATIOTHRESHOLD

 #define DEFAULT_VARCONSRATIOTHRESHOLD   1.0

minimum variable-constraint ratio on optimal face for separator execution

Definition at line 167 of file sepa_lagromory.c.

## ◆ DEFAULT_MINRESTART

 #define DEFAULT_MINRESTART   1

minimum restart round for separator execution (0: from beginning of the instance solving, >= n with n >= 1: from restart round n)

Definition at line 168 of file sepa_lagromory.c.

## ◆ DEFAULT_PERLPMAXCUTSROOT

 #define DEFAULT_PERLPMAXCUTSROOT   50

maximal number of cuts separated per Lagromory LP in the root node

Definition at line 171 of file sepa_lagromory.c.

## ◆ DEFAULT_PERLPMAXCUTS

 #define DEFAULT_PERLPMAXCUTS   10

maximal number of cuts separated per Lagromory LP in the non-root node

Definition at line 172 of file sepa_lagromory.c.

## ◆ DEFAULT_PERROUNDLPITERLIMITFACTOR

 #define DEFAULT_PERROUNDLPITERLIMITFACTOR   -1.0

factor w.r.t. root node LP iterations for maximal separating LP iterations per separation round (negative for no limit)

Definition at line 173 of file sepa_lagromory.c.

## ◆ DEFAULT_ROOTLPITERLIMITFACTOR

 #define DEFAULT_ROOTLPITERLIMITFACTOR   -1.0

factor w.r.t. root node LP iterations for maximal separating LP iterations in the root node (negative for no limit)

Definition at line 176 of file sepa_lagromory.c.

## ◆ DEFAULT_TOTALLPITERLIMITFACTOR

 #define DEFAULT_TOTALLPITERLIMITFACTOR   -1.0

factor w.r.t. root node LP iterations for maximal separating LP iterations in the tree (negative for no limit)

Definition at line 179 of file sepa_lagromory.c.

## ◆ DEFAULT_PERROUNDMAXLPITERS

 #define DEFAULT_PERROUNDMAXLPITERS   50000

maximal number of separating LP iterations per separation round (-1: unlimited)

Definition at line 182 of file sepa_lagromory.c.

## ◆ DEFAULT_PERROUNDCUTSFACTORROOT

 #define DEFAULT_PERROUNDCUTSFACTORROOT   1.0

factor w.r.t. number of integer columns for number of cuts separated per separation round in root node

Definition at line 183 of file sepa_lagromory.c.

## ◆ DEFAULT_PERROUNDCUTSFACTOR

 #define DEFAULT_PERROUNDCUTSFACTOR   0.5

factor w.r.t. number of integer columns for number of cuts separated per separation round at a non-root node

Definition at line 186 of file sepa_lagromory.c.

## ◆ DEFAULT_TOTALCUTSFACTOR

 #define DEFAULT_TOTALCUTSFACTOR   50.0

factor w.r.t. number of integer columns for total number of cuts separated

Definition at line 189 of file sepa_lagromory.c.

## ◆ DEFAULT_MAXMAINITERS

 #define DEFAULT_MAXMAINITERS   4

maximal number of main loop iterations of the relax-and-cut algorithm

Definition at line 190 of file sepa_lagromory.c.

## ◆ DEFAULT_MAXSUBGRADIENTITERS

 #define DEFAULT_MAXSUBGRADIENTITERS   6

maximal number of subgradient loop iterations of the relax-and-cut algorithm

Definition at line 191 of file sepa_lagromory.c.

## ◆ DEFAULT_MUPARAMCONST

 #define DEFAULT_MUPARAMCONST   TRUE

is the mu parameter (factor for step length) constant?

Definition at line 194 of file sepa_lagromory.c.

## ◆ DEFAULT_MUPARAMINIT

 #define DEFAULT_MUPARAMINIT   0.01

initial value of the mu parameter (factor for step length)

Definition at line 195 of file sepa_lagromory.c.

## ◆ DEFAULT_MUPARAMLB

 #define DEFAULT_MUPARAMLB   0.0

lower bound for the mu parameter (factor for step length)

Definition at line 196 of file sepa_lagromory.c.

## ◆ DEFAULT_MUPARAMUB

 #define DEFAULT_MUPARAMUB   2.0

upper bound for the mu parameter (factor for step length)

Definition at line 197 of file sepa_lagromory.c.

## ◆ DEFAULT_MUBACKTRACKFACTOR

 #define DEFAULT_MUBACKTRACKFACTOR   0.5

factor of mu while backtracking the mu parameter (factor for step length) - see updateMuSteplengthParam()

Definition at line 198 of file sepa_lagromory.c.

## ◆ DEFAULT_MUSLAB1FACTOR

 #define DEFAULT_MUSLAB1FACTOR   10.0

factor of mu parameter (factor for step length) for larger increment - see updateMuSteplengthParam()

Definition at line 201 of file sepa_lagromory.c.

## ◆ DEFAULT_MUSLAB2FACTOR

 #define DEFAULT_MUSLAB2FACTOR   2.0

factor of mu parameter (factor for step length) for smaller increment - see updateMuSteplengthParam()

Definition at line 204 of file sepa_lagromory.c.

## ◆ DEFAULT_MUSLAB3FACTOR

 #define DEFAULT_MUSLAB3FACTOR   0.5

factor of mu parameter (factor for step length) for reduction - see updateMuSteplengthParam()

Definition at line 207 of file sepa_lagromory.c.

## ◆ DEFAULT_DELTASLAB1UB

 #define DEFAULT_DELTASLAB1UB   0.001

factor of delta deciding larger increment of mu parameter (factor for step length) - see updateMuSteplengthParam()

Definition at line 210 of file sepa_lagromory.c.

## ◆ DEFAULT_DELTASLAB2UB

 #define DEFAULT_DELTASLAB2UB   0.01

factor of delta deciding smaller increment of mu parameter (factor for step length) - see updateMuSteplengthParam()

Definition at line 213 of file sepa_lagromory.c.

## ◆ DEFAULT_UBPARAMPOSFACTOR

 #define DEFAULT_UBPARAMPOSFACTOR   2.0

factor for positive upper bound used as an estimate for the optimal Lagrangian dual value

Definition at line 216 of file sepa_lagromory.c.

## ◆ DEFAULT_UBPARAMNEGFACTOR

 #define DEFAULT_UBPARAMNEGFACTOR   0.5

factor for negative upper bound used as an estimate for the optimal Lagrangian dual value

Definition at line 219 of file sepa_lagromory.c.

## ◆ DEFAULT_MAXLAGRANGIANVALSFORAVG

 #define DEFAULT_MAXLAGRANGIANVALSFORAVG   2

maximal number of iterations for rolling average of Lagrangian value

Definition at line 222 of file sepa_lagromory.c.

## ◆ DEFAULT_MAXCONSECITERSFORMUUPDATE

 #define DEFAULT_MAXCONSECITERSFORMUUPDATE   10

consecutive number of iterations used to determine if mu needs to be backtracked

Definition at line 223 of file sepa_lagromory.c.

## ◆ DEFAULT_PERROOTLPITERFACTOR

 #define DEFAULT_PERROOTLPITERFACTOR   0.2

factor w.r.t. root node LP iterations for iteration limit of each separating LP (negative for no limit)

Definition at line 224 of file sepa_lagromory.c.

## ◆ DEFAULT_PERLPITERFACTOR

 #define DEFAULT_PERLPITERFACTOR   0.1

factor w.r.t. non-root node LP iterations for iteration limit of each separating LP (negative for no limit)

Definition at line 227 of file sepa_lagromory.c.

## ◆ DEFAULT_CUTGENFREQ

 #define DEFAULT_CUTGENFREQ   1

frequency of subgradient iterations for generating cuts

Definition at line 230 of file sepa_lagromory.c.

## ◆ DEFAULT_CUTADDFREQ

 #define DEFAULT_CUTADDFREQ   1

frequency of subgradient iterations for adding cuts to objective function

Definition at line 231 of file sepa_lagromory.c.

## ◆ DEFAULT_CUTSFILTERFACTOR

 #define DEFAULT_CUTSFILTERFACTOR   1.0

fraction of generated cuts per explored basis to accept from separator

Definition at line 232 of file sepa_lagromory.c.

## ◆ DEFAULT_OPTIMALFACEPRIORITY

 #define DEFAULT_OPTIMALFACEPRIORITY   2

priority of the optimal face for separator execution (0: low priority, 1: medium priority, 2: high priority)

Definition at line 233 of file sepa_lagromory.c.

## ◆ DEFAULT_AGGREGATECUTS

 #define DEFAULT_AGGREGATECUTS   TRUE

aggregate all generated cuts using the Lagrangian multipliers?

Definition at line 236 of file sepa_lagromory.c.

## ◆ DEFAULT_PROJECTIONTYPE

 #define DEFAULT_PROJECTIONTYPE   2

the ball into which the Lagrangian multipliers are projected for stabilization (0: no projection, 1: L1-norm ball projection, 2: L2-norm ball projection, 3: L_inf-norm ball projection)

Definition at line 239 of file sepa_lagromory.c.

## ◆ DEFAULT_STABILITYCENTERTYPE

 #define DEFAULT_STABILITYCENTERTYPE   1

type of stability center for taking weighted average of Lagrangian multipliers for stabilization (0: no weighted stabilization, 1: best Lagrangian multipliers)

Definition at line 244 of file sepa_lagromory.c.

## ◆ DEFAULT_RADIUSINIT

 #define DEFAULT_RADIUSINIT   0.5

initial radius of the ball used in stabilization of Lagrangian multipliers

Definition at line 247 of file sepa_lagromory.c.

## ◆ DEFAULT_RADIUSMAX

 #define DEFAULT_RADIUSMAX   20.0

maximum radius of the ball used in stabilization of Lagrangian multipliers

Definition at line 248 of file sepa_lagromory.c.

## ◆ DEFAULT_RADIUSMIN

 #define DEFAULT_RADIUSMIN   1e-6

minimum radius of the ball used in stabilization of Lagrangian multipliers

Definition at line 249 of file sepa_lagromory.c.

## ◆ DEFAULT_CONST

 #define DEFAULT_CONST   2.0

a constant for stablity center based stabilization of Lagrangian multipliers

Definition at line 250 of file sepa_lagromory.c.

## ◆ DEFAULT_RADIUSUPDATEWEIGHT

 #define DEFAULT_RADIUSUPDATEWEIGHT   0.98

multiplier to evaluate cut violation score used for updating ball radius

Definition at line 251 of file sepa_lagromory.c.

## ◆ RANDSEED

 #define RANDSEED   42

random seed

Definition at line 254 of file sepa_lagromory.c.

## ◆ MAKECONTINTEGRAL

 #define MAKECONTINTEGRAL   FALSE

convert continuous variable to integral variables in SCIPmakeRowIntegral()?

Definition at line 255 of file sepa_lagromory.c.

Referenced by addCuts().

## ◆ POSTPROCESS

 #define POSTPROCESS   TRUE

apply postprocessing after MIR calculation? - see SCIPcalcMIR()

Definition at line 256 of file sepa_lagromory.c.

## ◆ BOUNDSWITCH

 #define BOUNDSWITCH   0.9999

threshold for bound switching - see SCIPcalcMIR()

Definition at line 257 of file sepa_lagromory.c.

## ◆ USEVBDS

 #define USEVBDS   TRUE

use variable bounds? - see SCIPcalcMIR()

Definition at line 258 of file sepa_lagromory.c.

## ◆ FIXINTEGRALRHS

 #define FIXINTEGRALRHS   FALSE

try to generate an integral rhs? - see SCIPcalcMIR()

Definition at line 259 of file sepa_lagromory.c.

## ◆ MAXAGGRLEN

 #define MAXAGGRLEN ( ncols ) (0.1*(ncols)+1000)

maximal length of base inequality

Definition at line 260 of file sepa_lagromory.c.

## ◆ createLPWithSoftCuts()

 static SCIP_RETCODE createLPWithSoftCuts ( SCIP * scip, SCIP_SEPADATA * sepadata )
static

start the diving mode for solving LPs corresponding to the Lagrangian dual with fixed multipliers in the subgradient loop of the separator, and update some sepadata values

Parameters
 scip SCIP data structure sepadata separator data structure

Definition at line 376 of file sepa_lagromory.c.

## ◆ deleteLPWithSoftCuts()

 static SCIP_RETCODE deleteLPWithSoftCuts ( SCIP * scip, SCIP_SEPADATA * sepadata )
static

end the diving mode that was used for solving LPs corresponding to the Lagrangian dual with fixed multipliers

Parameters
 scip SCIP data structure sepadata separator data structure

Definition at line 457 of file sepa_lagromory.c.

References SCIP_Real.

## ◆ createLPWithHardCuts()

 static SCIP_RETCODE createLPWithHardCuts ( SCIP * scip, SCIP_SEPADATA * sepadata, SCIP_ROW ** cuts, int ncuts )
static

set up LP interface to solve LPs in the (outer) main loop of the relax-and-cut algorithm; these LPs are built by adding all the generated cuts to the node relaxation

Parameters
 scip SCIP data structure sepadata separator data structure cuts generated cuts to be added to the LP ncuts number of generated cuts to be added to the LP

Definition at line 474 of file sepa_lagromory.c.

## ◆ sepadataFree()

 static SCIP_RETCODE sepadataFree ( SCIP * scip, SCIP_SEPADATA ** sepadata )
static

free separator data

Parameters
 scip SCIP data structure sepadata separator data structure

Definition at line 673 of file sepa_lagromory.c.

## ◆ updateMuSteplengthParam()

 static SCIP_RETCODE updateMuSteplengthParam ( SCIP * scip, SCIP_SEPADATA * sepadata, int subgradientiternum, SCIP_Real ubparam, SCIP_Real * lagrangianvals, SCIP_Real bestlagrangianval, SCIP_Real avglagrangianval, SCIP_Real * muparam, SCIP_Bool * backtrack )
static

update mu parameter which is used as a factor in the step length calculation; refer to the top of the file for a description of the formula.

Parameters
 scip SCIP data structure sepadata separator data structure subgradientiternum subgradient iteration number ubparam estimate of the optimal Lagrangian dual value lagrangianvals vector of Lagrangian values found so far bestlagrangianval best Lagrangian value found so far avglagrangianval rolling average of the Lagrangian values found so far muparam mu parameter to be updated backtrack whether mu parameter has been backtracked

Definition at line 709 of file sepa_lagromory.c.

Referenced by solveLagrangianDual().

## ◆ updateSubgradient()

 static void updateSubgradient ( SCIP * scip, SCIP_SOL * sol, SCIP_ROW ** cuts, int ncuts, SCIP_Real * subgradient, SCIP_Real * dualvector, SCIP_Bool * subgradientzero, int * ncutviols, SCIP_Real * maxcutviol, int * nnzsubgradientdualprod, SCIP_Real * maxnzsubgradientdualprod )
static

update subgradient, i.e., residuals of generated cuts

Note
assuming that $$i^{th}$$ cut is of the form $${\alpha^i}^T x \leq {\alpha^i_0}$$.
Parameters
 scip SCIP data structure sol LP solution used in updating subgradient vector cuts cuts generated so far ncuts number of cuts generated so far subgradient vector of subgradients to be updated dualvector Lagrangian multipliers subgradientzero whether the subgradient vector is all zero ncutviols number of violations of generated cuts maxcutviol maximum violation of generated cuts nnzsubgradientdualprod number of nonzero products of subgradient vector and Lagrangian multipliers (i.e., number of complementarity slackness violations) maxnzsubgradientdualprod maximum value of nonzero products of subgradient vector and Lagrangian multipliers (i.e., maximum value of complementarity slackness violations)

Definition at line 833 of file sepa_lagromory.c.

Referenced by solveLagrangianDual().

## ◆ updateLagrangianValue()

 static void updateLagrangianValue ( SCIP * scip, SCIP_Real objval, SCIP_Real * dualvector, SCIP_ROW ** cuts, int ncuts, SCIP_Real * lagrangianval )
static

update Lagrangian value, i.e., optimal value of the Lagrangian dual with fixed multipliers

Parameters
 scip SCIP data structure objval objective value of the Lagrangian dual with fixed multipliers dualvector Lagrangian multipliers cuts cuts generated so far ncuts number of cuts generated so far lagrangianval Lagrangian value to be updated

Definition at line 904 of file sepa_lagromory.c.

References SCIP_Real, SCIPisFeasZero(), and SQR.

Referenced by solveLagrangianDual().

## ◆ updateStepLength()

 static void updateStepLength ( SCIP * scip, SCIP_Real muparam, SCIP_Real ubparam, SCIP_Real lagrangianval, SCIP_Real * subgradient, int ncuts, SCIP_Real * steplength )
static

update step length based on various input arguments; refer to the top of the file for an expression

Parameters
 scip SCIP data structure muparam mu parameter used as a factor for step length ubparam estimate of the optimal Lagrangian dual value lagrangianval Lagrangian value subgradient subgradient vector ncuts number of cuts generated so far steplength step length to be updated

Definition at line 929 of file sepa_lagromory.c.

References NULL, and SCIP_Bool.

Referenced by solveLagrangianDual().

## ◆ updateBallRadius()

 static void updateBallRadius ( SCIP * scip, SCIP_SEPADATA * sepadata, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Real * ballradius )
static

update the ball radius (based on various violation metrics) that is used for stabilization of Lagrangian multipliers

Parameters
 scip SCIP data structure sepadata separator data structure maxviolscore weighted average of maximum value of generated cut violations and maximum value of complementarity slackness violations, in the current iteration maxviolscoreold weighted average of maximum value of generated cut violations and maximum value of complementarity slackness violations, in the previous iteration nviolscore weighted average of number of generated cut violations and number of complementarity slackness violations, in the current iteration nviolscoreold weighted average of number of generated cut violations and number of complementarity slackness violations, in the previous iteration nlpiters number of LP iterations taken for solving the Lagrangian dual with fixed multipliers in current iteration ballradius norm ball radius to be updated

Definition at line 951 of file sepa_lagromory.c.

Referenced by stabilizeDualVector().

## ◆ l1BallProjection()

 static SCIP_RETCODE l1BallProjection ( SCIP * scip, SCIP_Real * dualvector, int dualvectorlen, SCIP_Real radius )
static

projection of Lagrangian multipliers onto L1-norm ball. This algorithm is based on the following article

Condat L. (2016).
Fast projection onto the simplex and the $$l_1$$ ball.
Mathematical Programming, 158, 1-2, 575-585.

Parameters
 scip SCIP data structure dualvector Lagrangian multipliers to be projected onto L1-norm vall dualvectorlen length of the Lagrangian multipliers vector radius radius of the L1-norm ball

Definition at line 1020 of file sepa_lagromory.c.

Referenced by stabilizeDualVector().

## ◆ l2BallProjection()

 static void l2BallProjection ( SCIP * scip, SCIP_Real * dualvector, int dualvectorlen, SCIP_Real radius )
static

projection of Lagrangian multipliers onto L2-norm ball

Parameters
 scip SCIP data structure dualvector Lagrangian multipliers to be projected onto L2-norm vall dualvectorlen length of the Lagrangian multipliers vector radius radius of the L2-norm ball

Definition at line 1160 of file sepa_lagromory.c.

References linfBallProjection(), SCIP_Real, SCIPisGT(), SCIPisLT(), and SCIPisNegative().

Referenced by stabilizeDualVector().

## ◆ linfBallProjection()

 static void linfBallProjection ( SCIP * scip, SCIP_Real * dualvector, int dualvectorlen, SCIP_Real radius )
static

projection of Lagrangian multipliers onto L_infinity-norm ball

Parameters
 scip SCIP data structure dualvector Lagrangian multipliers to be projected onto L_infinity-norm vall dualvectorlen length of the Lagrangian multipliers vector radius radius of the L_infinity-norm ball

Definition at line 1191 of file sepa_lagromory.c.

References MAX, MIN, and SCIP_Real.

Referenced by l2BallProjection(), and stabilizeDualVector().

## ◆ weightedDualVector()

 static void weightedDualVector ( SCIP_SEPADATA * sepadata, SCIP_Real * dualvector, int dualvectorlen, SCIP_Real * stabilitycenter, int stabilitycenterlen, int nbestdualupdates, int totaliternum )
static

weighted Lagrangian multipliers based on a given vector as stability center

Parameters
 sepadata separator data structure dualvector Lagrangian multipliers dualvectorlen length of the Lagrangian multipliers vector stabilitycenter stability center (i.e., core vector of Lagrangian multipliers) stabilitycenterlen length of the stability center nbestdualupdates number of best Lagrangian values found so far totaliternum total number of iterations of the relax-and-cut algorithm performed so far

Definition at line 1217 of file sepa_lagromory.c.

Referenced by stabilizeDualVector().

## ◆ stabilizeDualVector()

 static SCIP_RETCODE stabilizeDualVector ( SCIP * scip, SCIP_SEPADATA * sepadata, SCIP_Real * dualvector, int dualvectorlen, SCIP_Real * bestdualvector, int bestdualvectorlen, int nbestdualupdates, int subgradientiternum, int totaliternum, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Real * ballradius )
static

stabilize Lagrangian multipliers

Parameters
 scip SCIP data structure sepadata separator data structure dualvector Lagrangian multipliers dualvectorlen length of the Lagrangian multipliers vector bestdualvector best Lagrangian multipliers found so far bestdualvectorlen length of the best Lagrangian multipliers vector nbestdualupdates number of best Lagrangian values found so far subgradientiternum iteration number of the subgradient algorithm totaliternum total number of iterations of the relax-and-cut algorithm performed so far maxviolscore weighted average of maximum value of generated cut violations and maximum value of complementarity slackness violations, in the current iteration maxviolscoreold weighted average of maximum value of generated cut violations and maximum value of complementarity slackness violations, in the previous iteration nviolscore weighted average of number of generated cut violations and number of complementarity slackness violations, in the current iteration nviolscoreold weighted average of number of generated cut violations and number of complementarity slackness violations, in the previous iteration nlpiters number of LP iterations taken for solving the Lagrangian dual with fixed multipliers in current iteration ballradius norm ball radius

Definition at line 1250 of file sepa_lagromory.c.

Referenced by updateDualVector().

## ◆ updateDualVector()

 static SCIP_RETCODE updateDualVector ( SCIP * scip, SCIP_SEPADATA * sepadata, SCIP_Real * dualvector1, SCIP_Real * dualvector2, int dualvector2len, int ndualvector2updates, int subgradientiternum, int totaliternum, SCIP_Real steplength, SCIP_Real * subgradient, int ncuts, SCIP_Bool backtrack, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Bool * dualvecsdiffer, SCIP_Real * ballradius )
static

update Lagrangian multipliers

Parameters
 scip SCIP data structure sepadata separator data structure dualvector1 Lagrangian multipliers vector to be updated dualvector2 Lagrangian multipliers vector used for backtracking dualvector2len length of the Lagrangian multipliers vector used for backtracking ndualvector2updates number of best Lagrangian values found so far subgradientiternum iteration number of the subgradient algorithm totaliternum total number of iterations of the relax-and-cut algorithm performed so far steplength step length used for updating Lagrangian multipliers subgradient subgradient vector ncuts number of generated cuts so far backtrack whether the Lagrangian multipliers need to be backtracked maxviolscore weighted average of maximum value of generated cut violations and maximum value of complementarity slackness violations, in the current iteration maxviolscoreold weighted average of maximum value of generated cut violations and maximum value of complementarity slackness violations, in the previous iteration nviolscore weighted average of number of generated cut violations and number of complementarity slackness violations, in the current iteration nviolscoreold weighted average of number of generated cut violations and number of complementarity slackness violations, in the previous iteration nlpiters number of LP iterations taken for solving the Lagrangian dual with fixed multipliers in current iteration dualvecsdiffer whether the updated Lagrangian multipliers differ from the old one ballradius norm ball radius

Definition at line 1310 of file sepa_lagromory.c.

Referenced by solveLagrangianDual(), and stabilizeDualVector().

## ◆ checkLagrangianDualTermination()

 static SCIP_RETCODE checkLagrangianDualTermination ( SCIP_SEPADATA * sepadata, int nnewaddedsoftcuts, int nyettoaddsoftcuts, SCIP_Bool objvecsdiffer, int ngeneratedcurrroundcuts, int nmaxgeneratedperroundcuts, int ncurrroundlpiters, int depth, SCIP_Bool * terminate )
static

check different termination criteria

Note
the criterion based on objvecsdiffer assumes deterministic solving process (i.e., we would get same LP solution for "Lagrangian dual with fixed Lagrangian multipliers" when the objective vector remains the same across iterations).
Parameters
 sepadata separator data structure nnewaddedsoftcuts number of cuts that were recently penalized and added to the Lagrangian dual's objective function nyettoaddsoftcuts number of cuts that are yet to be penalized and added to the Lagrangian dual's objective function objvecsdiffer whether the Lagrangian dual's objective function has changed ngeneratedcurrroundcuts number of cuts generated in the current separation round nmaxgeneratedperroundcuts maximal number of cuts allowed to generate per separation round ncurrroundlpiters number of separating LP iterations in the current separation round depth depth of the current node terminate whether to terminate the subgradient algorithm loop

Definition at line 1419 of file sepa_lagromory.c.

References SCIP_Bool, and SCIP_Real.

Referenced by solveLagrangianDual(), and updateDualVector().

## ◆ solveLagromoryLP()

 static SCIP_RETCODE solveLagromoryLP ( SCIP * scip, SCIP_SEPADATA * sepadata, int depth, SCIP_Real origobjoffset, SCIP_Bool * solfound, SCIP_SOL * sol, SCIP_Real * solvals, SCIP_Real * objval, int * ncurrroundlpiters )
static

solve the LP corresponding to the Lagrangian dual with fixed Lagrangian multipliers

Parameters
 scip SCIP data structure sepadata separator data structure depth depth of the current node in the tree origobjoffset objective offset in the current node's relaxation solfound whether an LP optimal solution has been found sol data structure to store LP optimal solution, if found solvals values of the LP optimal solution, if found objval optimal objective value of the LP optimal solution, if found ncurrroundlpiters number of LP iterations taken for solving Lagrangian dual problems with fixed multipliers in the current separator round

Definition at line 1466 of file sepa_lagromory.c.

Referenced by solveLagrangianDual().

## ◆ solveLPWithHardCuts()

 static SCIP_RETCODE solveLPWithHardCuts ( SCIP * scip, SCIP_SEPADATA * sepadata, SCIP_Bool * solfound, SCIP_SOL * sol, SCIP_Real * solvals )
static

solve the LP corresponding to the node relaxation upon adding all the generated cuts

Parameters
 scip SCIP data structure sepadata separator data structure solfound whether an LP optimal solution has been found sol data structure to store LP optimal solution, if found solvals values of the LP optimal solution, if found

Definition at line 1603 of file sepa_lagromory.c.

## ◆ constructCutRow()

 static SCIP_RETCODE constructCutRow ( SCIP * scip, SCIP_SEPA * sepa, SCIP_SEPADATA * sepadata, int mainiternum, int subgradientiternum, int cutnnz, int * cutinds, SCIP_Real * cutcoefs, SCIP_Real cutefficacy, SCIP_Real cutrhs, SCIP_Bool cutislocal, int cutrank, SCIP_ROW ** generatedcuts, SCIP_Real * generatedcutefficacies, int ngeneratedcurrroundcuts, int * ngeneratednewcuts, SCIP_Bool * cutoff )
static

construct a cut based on the input cut coefficients, sides, etc

Parameters
 scip SCIP data structure sepa pointer to the separator sepadata separator data structure mainiternum iteration number of the outer loop of the relax-and-cut algorithm subgradientiternum iteration number of the subgradient algorithm cutnnz number of nonzeros in cut cutinds column indices in cut cutcoefs cut cofficients cutefficacy cut efficacy cutrhs RHS of cut cutislocal whether cut is local cutrank rank of cut generatedcuts array of generated cuts generatedcutefficacies array of generated cut efficacies w.r.t. the respective LP bases used for cut generations ngeneratedcurrroundcuts number of cuts generated until the previous basis in the current separation round ngeneratednewcuts number of new cuts generated using the current basis cutoff should the current node be cutoff?

Definition at line 1667 of file sepa_lagromory.c.

## ◆ aggregateGeneratedCuts()

 static SCIP_RETCODE aggregateGeneratedCuts ( SCIP * scip, SCIP_SEPA * sepa, SCIP_SEPADATA * sepadata, SCIP_ROW ** generatedcuts, SCIP_Real * bestdualvector, int bestdualvectorlen, SCIP_ROW ** aggrcuts, int * naggrcuts, SCIP_Bool * cutoff )
static

aggregated generated cuts based on the best Lagrangian multipliers

Parameters
 scip SCIP data structure sepa pointer to the separator sepadata separator data structure generatedcuts cuts generated in the current separation round bestdualvector best Lagrangian multipliers vector bestdualvectorlen length of the best Lagrangian multipliers vector aggrcuts aggregated cuts generated so far in the current separation round naggrcuts number of aggregated cuts generated so far in the current separation round cutoff should the current node be cutoff?

Definition at line 1799 of file sepa_lagromory.c.

Referenced by constructCutRow().

## ◆ generateGMICuts()

 static SCIP_RETCODE generateGMICuts ( SCIP * scip, SCIP_SEPA * sepa, SCIP_SEPADATA * sepadata, int mainiternum, int subgradientiternum, SCIP_SOL * sol, SCIP_Real * solvals, int nmaxgeneratedperroundcuts, SCIP_Bool allowlocal, SCIP_ROW ** generatedcurrroundcuts, SCIP_Real * generatedcutefficacies, int ngeneratedcurrroundcuts, int * ngeneratednewcuts, int depth, SCIP_Bool * cutoff )
static

main method: LP solution separation method of separator

Parameters
 scip SCIP data structure sepa pointer to the separator sepadata separator data structure mainiternum iteration number of the outer loop of the relax-and-cut algorithm subgradientiternum iteration number of the subgradient algorithm sol LP solution to be used for cut generation solvals values of the LP solution to be used for cut generation nmaxgeneratedperroundcuts maximal number of cuts allowed to generate per separation round allowlocal should locally valid cuts be generated? generatedcurrroundcuts cuts generated in the current separation round generatedcutefficacies array of generated cut efficacies w.r.t. the respective LP bases used for cut generations ngeneratedcurrroundcuts number of cuts generated until the previous basis in the current separation round ngeneratednewcuts number of new cuts generated using the current basis depth depth of the current node in the tree cutoff should the current node be cutoff?

Definition at line 2022 of file sepa_lagromory.c.

Referenced by solveLagrangianDual().

## ◆ updateObjectiveVector()

 static SCIP_RETCODE updateObjectiveVector ( SCIP * scip, SCIP_Real * dualvector, SCIP_ROW ** cuts, int ncuts, SCIP_Real * origobjcoefs, SCIP_Bool * objvecsdiffer )
static

update objective vector w.r.t. the fixed Lagrangian multipliers

Parameters
 scip SCIP data structure dualvector Lagrangian multipliers vector cuts cuts generated so far in the current separation round ncuts number of cuts generated so far in the current separation round origobjcoefs original objective function coefficients of the node linear relaxation objvecsdiffer whether the updated objective function coefficients differ from the old ones

Definition at line 2212 of file sepa_lagromory.c.

Referenced by solveLagrangianDual().

## ◆ addGMICutsAsSoftConss()

 static SCIP_RETCODE addGMICutsAsSoftConss ( SCIP_Real * dualvector, int ngeneratedcuts, int * naddedcuts, int * nnewaddedsoftcuts )
static

add GMI cuts to the objective function of the Lagrangian dual problem by introducing new Lagrangian multipliers

Parameters
 dualvector Lagrangian multipliers vector ngeneratedcuts number of cuts generated so far in the current separation round naddedcuts number of cuts added so far in the current separation round to the Lagrangian dual problem upon penalization nnewaddedsoftcuts number of cuts added newly to the Lagrangian dual problem upon penalization

Definition at line 2297 of file sepa_lagromory.c.

Referenced by solveLagrangianDual().

## ◆ solveLagrangianDual()

 static SCIP_RETCODE solveLagrangianDual ( SCIP * scip, SCIP_SEPA * sepa, SCIP_SEPADATA * sepadata, SCIP_SOL * sol, SCIP_Real * solvals, int mainiternum, SCIP_Real ubparam, int depth, SCIP_Bool allowlocal, int nmaxgeneratedperroundcuts, SCIP_Real * origobjcoefs, SCIP_Real origobjoffset, SCIP_Real * dualvector, int * nsoftcuts, SCIP_ROW ** generatedcurrroundcuts, SCIP_Real * generatedcutefficacies, int * ngeneratedcutsperiter, int * ngeneratedcurrroundcuts, int * ncurrroundlpiters, SCIP_Bool * cutoff, SCIP_Real * bestlagrangianval, SCIP_Real * bestdualvector, int * bestdualvectorlen, int * nbestdualupdates, int * totaliternum )
static

solve the Lagrangian dual problem

Parameters
 scip SCIP data structure sepa pointer to the separator sepadata separator data structure sol data structure to store an LP solution upon solving a Lagrangian dual problem with fixed Lagrangian multipliers solvals values of the LP solution obtained upon solving a Lagrangian dual problem with fixed Lagrangian multipliers mainiternum iteration number of the outer loop of the relax-and-cut algorithm ubparam estimate of the optimal Lagrangian dual value depth depth of the current node in the tree allowlocal should locally valid cuts be generated? nmaxgeneratedperroundcuts maximal number of cuts allowed to generate per separation round origobjcoefs original objective function coefficients of the node linear relaxation origobjoffset original objective function offset of the node linear relaxation dualvector Lagrangian multipliers vector nsoftcuts number of generated cuts that were penalized and added to the Lagrangian dual problem generatedcurrroundcuts cuts generated in the current separation round generatedcutefficacies array of generated cut efficacies w.r.t. the respective LP bases used for cut generations ngeneratedcutsperiter number of cuts generated per subgradient iteration in the current separation round ngeneratedcurrroundcuts number of cuts generated so far in the current separation round ncurrroundlpiters number of LP iterations taken for solving Lagrangian dual problems with fixed multipliers in the current separator round cutoff should the current node be cutoff? bestlagrangianval best Lagrangian value found so far bestdualvector Lagrangian multipliers corresponding to the best Lagrangian value found so far bestdualvectorlen length of the Lagrangian multipliers corresponding to the best Lagrangian value found so far nbestdualupdates number of best Lagrangian values found so far totaliternum total number of iterations of the relax-and-cut algorithm performed so far

Definition at line 2321 of file sepa_lagromory.c.

## ◆ generateInitCutPool()

 static SCIP_RETCODE generateInitCutPool ( SCIP * scip, SCIP_SEPA * sepa, SCIP_SEPADATA * sepadata, int mainiternum, SCIP_SOL * sol, SCIP_Real * solvals, int nmaxgeneratedperroundcuts, SCIP_Bool allowlocal, SCIP_ROW ** generatedcurrroundcuts, SCIP_Real * generatedcutefficacies, int * ngeneratedcutsperiter, int * ngeneratedcurrroundcuts, int depth, SCIP_Bool * cutoff )
static

generates initial cut pool before solving the Lagrangian dual

Parameters
 scip SCIP data structure sepa separator sepadata separator data structure mainiternum iteration number of the outer loop of the relax-and-cut algorithm sol LP solution to be used for cut generation solvals values of the LP solution to be used for cut generation nmaxgeneratedperroundcuts maximal number of cuts allowed to generate per separation round allowlocal should locally valid cuts be generated? generatedcurrroundcuts cuts generated in the current separation round generatedcutefficacies array of generated cut efficacies w.r.t. the respective LP bases used for cut generations ngeneratedcutsperiter number of cuts generated per subgradient iteration in the current separation round ngeneratedcurrroundcuts number of cuts generated so far in the current separation round depth depth of the current node in the tree cutoff should the current node be cutoff?

Definition at line 2559 of file sepa_lagromory.c.

Referenced by solveLagrangianDual().

## ◆ addCuts()

 static SCIP_RETCODE addCuts ( SCIP * scip, SCIP_SEPADATA * sepadata, SCIP_ROW ** cuts, int ncuts, SCIP_Longint maxdnom, SCIP_Real maxscale, int * naddedcuts, SCIP_Bool * cutoff )
static

add cuts to SCIP

Parameters
 scip SCIP data structure sepadata separator data structure cuts cuts generated so far in the current separation round ncuts number of cuts generated so far in the current separation round maxdnom maximum denominator in the rational representation of cuts maxscale maximal scale factor to scale the cuts to integral values naddedcuts number of cuts added to either global cutpool or sepastore cutoff should the current node be cutoff?

Definition at line 2596 of file sepa_lagromory.c.

## ◆ checkMainLoopTermination()

 static SCIP_RETCODE checkMainLoopTermination ( SCIP_SEPADATA * sepadata, SCIP_Bool cutoff, SCIP_Bool dualvecsdiffer, int ngeneratedcurrroundcuts, int nsoftcuts, int nmaxgeneratedperroundcuts, int ncurrroundlpiters, int depth, SCIP_Bool * terminate )
static

check different termination criteria

Parameters
 sepadata separator data structure cutoff should the current node be cutoff? dualvecsdiffer whether the updated Lagrangian multipliers differ from the old one ngeneratedcurrroundcuts number of cuts generated in the current separation round nsoftcuts number of generated cuts that were penalized and added to the Lagrangian dual problem nmaxgeneratedperroundcuts maximal number of cuts allowed to generate per separation round ncurrroundlpiters number of LP iterations taken for solving Lagrangian dual problems with fixed multipliers in the current separator round depth depth of the current node in the tree terminate whether to terminate the relax-and-cut algorithm

Definition at line 2673 of file sepa_lagromory.c.

References SCIP_Bool, and SCIP_Real.

Referenced by addCuts().

## ◆ separateCuts()

 static SCIP_RETCODE separateCuts ( SCIP * scip, SCIP_SEPA * sepa, SCIP_SEPADATA * sepadata, SCIP_Real ubparam, int depth, SCIP_Bool allowlocal, SCIP_RESULT * result )
static

searches and tries to add Lagromory cuts

Parameters
 scip SCIP data structure sepa separator sepadata separator data structure ubparam estimate of the optimal Lagrangian dual value depth depth of the current node in the tree allowlocal should locally valid cuts be generated? result final result of the separation round

Definition at line 2721 of file sepa_lagromory.c.

## ◆ sepadataCreate()

 static SCIP_RETCODE sepadataCreate ( SCIP * scip, SCIP_SEPADATA ** sepadata )
static

creates separator data

Parameters
 scip SCIP data structure sepadata separator data structure

Definition at line 3041 of file sepa_lagromory.c.

## ◆ SCIP_DECL_SEPACOPY()

 static SCIP_DECL_SEPACOPY ( sepaCopyLagromory )
static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 3062 of file sepa_lagromory.c.

## ◆ SCIP_DECL_SEPAFREE()

 static SCIP_DECL_SEPAFREE ( sepaFreeLagromory )
static

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

Definition at line 3077 of file sepa_lagromory.c.

Referenced by sepadataCreate().

## ◆ SCIP_DECL_SEPAINIT()

 static SCIP_DECL_SEPAINIT ( sepaInitLagromory )
static

initialization method of separator (called after problem was transformed)

Definition at line 3093 of file sepa_lagromory.c.

References NULL, SCIP_DECL_SEPAEXECLP(), SCIP_OKAY, SCIPfreeRandom(), and SCIPsepaGetData().

## ◆ SCIP_DECL_SEPAEXIT()

 static SCIP_DECL_SEPAEXIT ( sepaExitLagromory )
static

deinitialization method of separator (called before transformed problem is freed)

Definition at line 3113 of file sepa_lagromory.c.

## ◆ SCIP_DECL_SEPAEXECLP()

 static SCIP_DECL_SEPAEXECLP ( sepaExeclpLagromory )
static

LP solution separation method of separator

Definition at line 3127 of file sepa_lagromory.c.

Referenced by SCIP_DECL_SEPAINIT().