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, \ldots, 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.
- 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:
- Solve the Lagrangian dual problem until certain termination criterion is met. This results in an inner subgradient loop, whose iteration \(j\) is described below.
- 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 isubparam, and \(s^j\) is the subgradient vector defined as:\[ s^j_k = \left({\alpha^k}^T x - \alpha^k_0\right), k = 1, 2, \ldots, M. \]
The factor \(mu_j\) is updated as below.\[ mu_j = \begin{cases} mubacktrackfactor * mu_j & \text{if } L(u^j) < bestLB - \delta\\ \begin{cases} muslab1factor * mu_j & \text{if } bestLB - avgLB < deltaslab1ub * delta\\ muslab2factor * mu_j & \text{if } deltaslab1ub * \delta \leq bestLB - avgLB < deltaslab2ub * delta\\ 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\).
- 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\).
- Solve the Lagrangian dual problem until certain termination criterion is met. This results in an inner subgradient loop, whose iteration \(j\) is described below.
Definition in file sepa_lagromory.c.
Go to the source code of this file.
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) |
Macro Definition Documentation
◆ SEPA_NAME
| #define SEPA_NAME "lagromory" |
Definition at line 138 of file sepa_lagromory.c.
◆ SEPA_DESC
| #define SEPA_DESC "separator for Lagromory cuts for MIP relaxations" |
Definition at line 139 of file sepa_lagromory.c.
◆ SEPA_PRIORITY
| #define SEPA_PRIORITY -8000 |
Definition at line 140 of file sepa_lagromory.c.
◆ SEPA_FREQ
| #define SEPA_FREQ -1 |
Definition at line 141 of file sepa_lagromory.c.
◆ SEPA_MAXBOUNDDIST
| #define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 142 of file sepa_lagromory.c.
◆ SEPA_USESSUBSCIP
| #define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 143 of file sepa_lagromory.c.
◆ SEPA_DELAY
| #define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 144 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 147 of file sepa_lagromory.c.
◆ DEFAULT_DELAYEDCUTS
| #define DEFAULT_DELAYEDCUTS FALSE |
should cuts be added to the delayed cut pool?
Definition at line 148 of file sepa_lagromory.c.
◆ DEFAULT_SEPARATEROWS
| #define DEFAULT_SEPARATEROWS TRUE |
separate rows with integral slack?
Definition at line 149 of file sepa_lagromory.c.
◆ DEFAULT_SORTCUTOFFSOL
| #define DEFAULT_SORTCUTOFFSOL TRUE |
sort fractional integer columns based on fractionality?
Definition at line 150 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 151 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 152 of file sepa_lagromory.c.
◆ DEFAULT_MAKEINTEGRAL
| #define DEFAULT_MAKEINTEGRAL FALSE |
try to scale all cuts to integral coefficients?
Definition at line 153 of file sepa_lagromory.c.
◆ DEFAULT_FORCECUTS
| #define DEFAULT_FORCECUTS FALSE |
force cuts to be added to the LP?
Definition at line 154 of file sepa_lagromory.c.
◆ DEFAULT_ALLOWLOCAL
| #define DEFAULT_ALLOWLOCAL FALSE |
should locally valid cuts be generated?
Definition at line 155 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 158 of file sepa_lagromory.c.
◆ DEFAULT_MAXROUNDS
| #define DEFAULT_MAXROUNDS 1 |
maximal number of separation rounds per node (-1: unlimited)
Definition at line 159 of file sepa_lagromory.c.
◆ DEFAULT_DUALDEGENERACYRATETHRESHOLD
| #define DEFAULT_DUALDEGENERACYRATETHRESHOLD 0.5 |
minimum dual degeneracy rate for separator execution
Definition at line 160 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 161 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 163 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 164 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 165 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 167 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 169 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 171 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 172 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 174 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 176 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 177 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 178 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 179 of file sepa_lagromory.c.
◆ DEFAULT_MUPARAMCONST
| #define DEFAULT_MUPARAMCONST TRUE |
is the mu parameter (factor for step length) constant?
Definition at line 182 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 183 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 184 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 185 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 187 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 189 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 191 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 193 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 195 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 197 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 199 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 201 of file sepa_lagromory.c.
◆ DEFAULT_MAXLAGRANGIANVALSFORAVG
| #define DEFAULT_MAXLAGRANGIANVALSFORAVG 2 |
maximal number of iterations for rolling average of Lagrangian value
Definition at line 202 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 203 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 205 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 207 of file sepa_lagromory.c.
◆ DEFAULT_CUTGENFREQ
| #define DEFAULT_CUTGENFREQ 1 |
frequency of subgradient iterations for generating cuts
Definition at line 208 of file sepa_lagromory.c.
◆ DEFAULT_CUTADDFREQ
| #define DEFAULT_CUTADDFREQ 1 |
frequency of subgradient iterations for adding cuts to objective function
Definition at line 209 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 210 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 212 of file sepa_lagromory.c.
◆ DEFAULT_AGGREGATECUTS
| #define DEFAULT_AGGREGATECUTS TRUE |
aggregate all generated cuts using the Lagrangian multipliers?
Definition at line 213 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 218 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 220 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 221 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 222 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 223 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 224 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 225 of file sepa_lagromory.c.
◆ RANDSEED
| #define RANDSEED 42 |
random seed
Definition at line 228 of file sepa_lagromory.c.
◆ MAKECONTINTEGRAL
| #define MAKECONTINTEGRAL FALSE |
convert continuous variable to integral variables in SCIPmakeRowIntegral()?
Definition at line 229 of file sepa_lagromory.c.
◆ POSTPROCESS
| #define POSTPROCESS TRUE |
apply postprocessing after MIR calculation? - see SCIPcalcMIR()
Definition at line 230 of file sepa_lagromory.c.
◆ BOUNDSWITCH
| #define BOUNDSWITCH 0.9999 |
threshold for bound switching - see SCIPcalcMIR()
Definition at line 231 of file sepa_lagromory.c.
◆ VARTYPEUSEVBDS
| #define VARTYPEUSEVBDS 2 |
We allow variable bound substitution for variables with continuous vartype only. See SCIPcalcMIR() for more information.
Definition at line 233 of file sepa_lagromory.c.
◆ FIXINTEGRALRHS
| #define FIXINTEGRALRHS FALSE |
try to generate an integral rhs? - see SCIPcalcMIR()
Definition at line 234 of file sepa_lagromory.c.
◆ MAXAGGRLEN
| #define MAXAGGRLEN | ( | ncols | ) | (0.1*(ncols)+1000) |
maximal length of base inequality
Definition at line 235 of file sepa_lagromory.c.
Function Documentation
◆ createLPWithSoftCuts()
|
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 351 of file sepa_lagromory.c.
References MIN, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPcolIsIntegral(), SCIPgetLPColsData(), SCIPgetLPI(), SCIPgetLPRowsData(), SCIPgetNRootFirstLPIterations(), SCIPgetNRuns(), SCIPisInfinity(), and SCIPstartDive().
Referenced by separateCuts().
◆ deleteLPWithSoftCuts()
|
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 432 of file sepa_lagromory.c.
References NULL, SCIP_CALL, SCIP_OKAY, and SCIPendDive().
Referenced by separateCuts().
◆ createLPWithHardCuts()
|
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 449 of file sepa_lagromory.c.
References NULL, SCIP_CALL, SCIP_OBJSEN_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetObj(), SCIPcolGetUb(), SCIPfreeBufferArray, SCIPgetLPColsData(), SCIPgetLPI(), SCIPgetLPRowsData(), SCIPgetMessagehdlr(), SCIPisInfinity(), SCIPlpiAddCols(), SCIPlpiAddRows(), SCIPlpiCreate(), SCIPlpiFree(), SCIPlpiFreeState(), SCIPlpiGetState(), SCIPlpiInfinity(), SCIPlpiSetState(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetNNonz(), SCIProwGetRhs(), and SCIProwGetVals().
Referenced by separateCuts().
◆ sepadataFree()
|
static |
free separator data
- Parameters
-
scip SCIP data structure sepadata separator data structure
Definition at line 648 of file sepa_lagromory.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPlpiFree().
Referenced by SCIP_DECL_SEPAFREE().
◆ updateMuSteplengthParam()
|
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 684 of file sepa_lagromory.c.
References FALSE, MAX, MIN, NULL, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisPositive(), and TRUE.
Referenced by solveLagrangianDual().
◆ updateSubgradient()
|
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 808 of file sepa_lagromory.c.
References FALSE, MAX, NULL, REALABS, SCIP_Real, SCIPgetRowSolActivity(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisZero(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetRhs(), and TRUE.
Referenced by solveLagrangianDual().
◆ updateLagrangianValue()
|
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 879 of file sepa_lagromory.c.
References NULL, SCIPisInfinity(), SCIProwGetConstant(), SCIProwGetLhs(), and SCIProwGetRhs().
Referenced by solveLagrangianDual().
◆ updateStepLength()
|
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 904 of file sepa_lagromory.c.
References SCIP_Real, SCIPisFeasZero(), and SQR.
Referenced by solveLagrangianDual().
◆ updateBallRadius()
|
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 926 of file sepa_lagromory.c.
References MAX, MIN, NULL, SCIP_Bool, and SCIPisNegative().
Referenced by stabilizeDualVector().
◆ l1BallProjection()
|
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 995 of file sepa_lagromory.c.
References FALSE, MAX, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisGT(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), and TRUE.
Referenced by stabilizeDualVector().
◆ l2BallProjection()
|
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 1135 of file sepa_lagromory.c.
References SCIP_Real, SCIPisGT(), SCIPisLT(), SCIPisNegative(), and SQR.
Referenced by stabilizeDualVector().
◆ linfBallProjection()
|
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 1166 of file sepa_lagromory.c.
References SCIPisGT(), SCIPisLT(), and SCIPisNegative().
Referenced by stabilizeDualVector().
◆ weightedDualVector()
|
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 1192 of file sepa_lagromory.c.
References MAX, MIN, and SCIP_Real.
Referenced by stabilizeDualVector().
◆ stabilizeDualVector()
|
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 1225 of file sepa_lagromory.c.
References l1BallProjection(), l2BallProjection(), linfBallProjection(), SCIP_CALL, SCIP_OKAY, updateBallRadius(), and weightedDualVector().
Referenced by updateDualVector().
◆ updateDualVector()
|
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 1285 of file sepa_lagromory.c.
References FALSE, MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPisEQ(), stabilizeDualVector(), and TRUE.
Referenced by separateCuts(), and solveLagrangianDual().
◆ checkLagrangianDualTermination()
|
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 1394 of file sepa_lagromory.c.
References FALSE, SCIP_OKAY, and TRUE.
Referenced by solveLagrangianDual().
◆ solveLagromoryLP()
|
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 1441 of file sepa_lagromory.c.
References FALSE, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LPPAR_LPTILIM, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPdebugMsg, SCIPgetLPColsData(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), SCIPgetNNodeInitLPIterations(), SCIPgetNRootFirstLPIterations(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPisLPSolBasic(), SCIPlpiSetRealpar(), SCIPsetSolVal(), SCIPsolveDiveLP(), and TRUE.
Referenced by separateCuts(), and solveLagrangianDual().
◆ solveLPWithHardCuts()
|
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 1578 of file sepa_lagromory.c.
References FALSE, NULL, SCIP_CALL, SCIP_LPPAR_LPTILIM, SCIP_OKAY, SCIP_Real, SCIPcolGetVar(), SCIPdebugMsg, SCIPgetLPColsData(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPlpiGetSol(), SCIPlpiIsPrimalFeasible(), SCIPlpiSetRealpar(), SCIPlpiSolvePrimal(), SCIPsetSolVal(), and TRUE.
Referenced by separateCuts().
◆ constructCutRow()
|
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 1642 of file sepa_lagromory.c.
References FALSE, NULL, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcolGetVar(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetLPCols(), SCIPgetRowMaxActivity(), SCIPgetRowMinActivity(), SCIPinfinity(), SCIPisEfficacious(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIProwChgRank(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwIsModifiable(), SCIPsepaGetName(), SCIPsnprintf(), and TRUE.
Referenced by generateGMICuts().
◆ aggregateGeneratedCuts()
|
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 1774 of file sepa_lagromory.c.
References FALSE, MAX, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_SIZE, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPcacheRowExtensions(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetLPColsData(), SCIPgetRowMaxActivity(), SCIPgetRowMinActivity(), SCIPinfinity(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGE(), SCIPisInfinity(), SCIPisZero(), SCIPquadprecProdDD, SCIPquadprecSumQQ, SCIProwChgRank(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsepaGetName(), SCIPsnprintf(), and TRUE.
Referenced by separateCuts().
◆ generateGMICuts()
|
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 1997 of file sepa_lagromory.c.
References BOUNDSWITCH, constructCutRow(), FIXINTEGRALRHS, MAXAGGRLEN, MIN, NULL, POSTPROCESS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPaggrRowSumRows(), SCIPallocBufferArray, SCIPcalcMIR(), SCIPcolGetVar(), SCIPfeasFrac(), SCIPfreeBufferArray, SCIPgetLPBasisInd(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetRowActivity(), SCIPisStopped(), SCIPrandomGetReal(), SCIProwIsIntegral(), SCIProwIsModifiable(), SCIPsortDownRealInt(), SCIPvarIsIntegral(), and VARTYPEUSEVBDS.
Referenced by generateInitCutPool(), and solveLagrangianDual().
◆ updateObjectiveVector()
|
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 2187 of file sepa_lagromory.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPchgVarObjDive(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetLPColsData(), SCIPgetVarObjDive(), SCIPisEQ(), SCIPisInfinity(), SCIPisZero(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), and TRUE.
Referenced by solveLagrangianDual().
◆ addGMICutsAsSoftConss()
|
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 2272 of file sepa_lagromory.c.
References SCIP_OKAY.
Referenced by solveLagrangianDual().
◆ solveLagrangianDual()
|
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 2296 of file sepa_lagromory.c.
References addGMICutsAsSoftConss(), checkLagrangianDualTermination(), FALSE, generateGMICuts(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisPositive(), SCIPisStopped(), solveLagromoryLP(), TRUE, updateDualVector(), updateLagrangianValue(), updateMuSteplengthParam(), updateObjectiveVector(), updateStepLength(), and updateSubgradient().
Referenced by separateCuts().
◆ generateInitCutPool()
|
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 2530 of file sepa_lagromory.c.
References generateGMICuts(), SCIP_CALL, and SCIP_OKAY.
Referenced by separateCuts().
◆ addCuts()
|
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 2567 of file sepa_lagromory.c.
References FALSE, MAKECONTINTEGRAL, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddDelayedPoolCut(), SCIPaddPoolCut(), SCIPaddRow(), SCIPepsilon(), SCIPgetRowNumIntCols(), SCIPisCutNew(), SCIPisInfinity(), SCIPmakeRowIntegral(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPsumepsilon(), and TRUE.
Referenced by separateCuts().
◆ checkMainLoopTermination()
|
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 2644 of file sepa_lagromory.c.
References FALSE, SCIP_OKAY, and TRUE.
Referenced by separateCuts().
◆ separateCuts()
|
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 2692 of file sepa_lagromory.c.
References addCuts(), aggregateGeneratedCuts(), checkMainLoopTermination(), createLPWithHardCuts(), createLPWithSoftCuts(), deleteLPWithSoftCuts(), FALSE, generateInitCutPool(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPceil(), SCIPcolGetObj(), SCIPcreateSol(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPfreeSol(), SCIPgetLPColsData(), SCIPgetMaxDepth(), SCIPgetNLPRows(), SCIPgetTransObjoffset(), SCIPheurPassSolTrySol(), SCIPinfinity(), SCIPisGE(), SCIPisPositive(), SCIPisStopped(), SCIPlpiGetSol(), SCIPlpiIsDualFeasible(), SCIPlpiWasSolved(), SCIPreleaseRow(), SCIPsepaGetNCalls(), SCIPsortDownRealInt(), solveLagrangianDual(), solveLagromoryLP(), solveLPWithHardCuts(), TRUE, and updateDualVector().
Referenced by SCIP_DECL_SEPAEXECLP().
◆ sepadataCreate()
|
static |
creates separator data
- Parameters
-
scip SCIP data structure sepadata separator data structure
Definition at line 3011 of file sepa_lagromory.c.
References BMSclearMemory, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by SCIPincludeSepaLagromory().
◆ SCIP_DECL_SEPACOPY()
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 3032 of file sepa_lagromory.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaLagromory(), SCIPsepaGetName(), and SEPA_NAME.
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 3047 of file sepa_lagromory.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), SCIPsepaSetData(), and sepadataFree().
◆ SCIP_DECL_SEPAINIT()
|
static |
initialization method of separator (called after problem was transformed)
Definition at line 3063 of file sepa_lagromory.c.
References NULL, RANDSEED, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPfindHeur(), SCIPsepaGetData(), and TRUE.
◆ SCIP_DECL_SEPAEXIT()
|
static |
deinitialization method of separator (called before transformed problem is freed)
Definition at line 3083 of file sepa_lagromory.c.
References NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPsepaGetData().
◆ SCIP_DECL_SEPAEXECLP()
|
static |
LP solution separation method of separator
Definition at line 3097 of file sepa_lagromory.c.
References NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPcolGetObj(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPgetBestSol(), SCIPgetLPColsData(), SCIPgetLPDualDegeneracy(), SCIPgetLPSolstat(), SCIPgetNLPRows(), SCIPgetNRuns(), SCIPgetSolVal(), SCIPgetTransObjoffset(), SCIPisLPSolBasic(), SCIPisPositive(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SEPA_NAME, and separateCuts().