SCIP Doxygen Documentation
Loading...
Searching...
No Matches
sepa_lagromory.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file sepa_lagromory.c
26 * @ingroup DEFPLUGINS_SEPA
27 * @brief Lagromory separator
28 * @author Suresh Bolusani
29 * @author Mark Ruben Turner
30 * @author Mathieu Besançon
31 *
32 * This separator is based on the following article that discusses Lagromory separation using the relax-and-cut
33 * framework. Multiple enhancements have been implemented on top of the basic algorithm described in the article.
34 *
35 * Fischetti M. and Salvagnin D. (2011).@n
36 * A relax-and-cut framework for Gomory mixed-integer cuts.@n
37 * Mathematical Programming Computation, 3, 79-102.
38 *
39 * Consider the following linear relaxation at a node:
40 *
41 * \f[
42 * \begin{array}{rrl}
43 * \min & c^T x &\\
44 * & x & \in P,
45 * \end{array}
46 * \f]
47 *
48 * where \f$P\f$ is the feasible region of the relaxation. Let the following be the cuts generated so far in the current
49 * separation round.
50 *
51 * \f[
52 * {\alpha^i}^T x \leq \alpha^i_0, i = 1, 2, \ldots, M
53 * \f]
54 *
55 * Then, the following is the Lagrangian dual problem considered in the relax-and-cut framework used in the separator.
56 *
57 * \f[
58 * z_D := \max\limits_{u \geq 0} \left\{L(u) := \min \left\{c^T x + \sum\limits_{i = 1}^{M} \left(u_i
59 * \left({\alpha^i}^T x - \alpha^i_0\right) \right) \mid x \in P\right\} \right\},
60 * \f]
61 *
62 * where \f$u\f$ are the Lagrangian multipliers (referred to as \a dualvector in this separator) used for penalizing the
63 * violation of the generated cuts, and \f$z_D\f$ is the optimal objective value (which is approximated via \a ubparam in this separator).
64 * Then, the following are the steps of the relax-and-cut algorithm implemented in this separator.
65 *
66 * - Generate an initial pool of cuts to build the initial Lagrangian dual problem.
67 * - Select initial values for Lagrangian multipliers \f$u^0\f$ (e.g., all zeroes vector).
68 * - In the outer main loop \f$i\f$ of the algorithm:
69 * 1. Solve the Lagrangian dual problem until certain termination criterion is met. This results in an inner
70 * subgradient loop, whose iteration \f$j\f$ is described below.
71 * 1. Fix \f$u^j\f$, and solve the LP corresponding to the Lagrangian dual with fixed multipliers.
72 * Gather its optimal simplex tableau and optimal objective value (i.e., the Lagrangian value)
73 * \f$L(u^j)\f$.
74 * 2. Update \f$u^j\f$ to \f$u^{j+1}\f$ as follows.
75 * \f[
76 * u^{j+1} = \left(u^j + \lambda_j s^k\right)_+,
77 * \f]
78 * where \f$\lambda_j\f$ is the step length:
79 * \f[
80 * \lambda_j = \frac{\mu_j (UB - L(u^j))}{\|s^j\|^2_2},
81 * \f]
82 * where \f$mu_j\f$ is a factor (i.e., \a muparam) such that \f$0 < \mu_j \leq 2\f$, UB is \p ubparam,
83 * and \f$s^j\f$ is the subgradient vector defined as:
84 * \f[
85 * s^j_k = \left({\alpha^k}^T x - \alpha^k_0\right), k = 1, 2, \ldots, M.
86 * \f]
87 * The factor \f$mu_j\f$ is updated as below.
88 * \f[
89 * mu_j = \begin{cases}
90 * mubacktrackfactor * mu_j & \text{if } L(u^j) < bestLB - \delta\\
91 * \begin{cases}
92 * muslab1factor * mu_j & \text{if } bestLB - avgLB < deltaslab1ub * delta\\
93 * muslab2factor * mu_j & \text{if } deltaslab1ub * \delta \leq bestLB - avgLB < deltaslab2ub * delta\\
94 * muslab3factor * mu_j & \text{otherwise}
95 * \end{cases} & \text{otherwise},
96 * \end{cases}
97 * \f]
98 * where \f$bestLB\f$ and \f$avgLB\f$ are best and average Lagrangian values found so far, and
99 * \f$\delta = UB - bestLB\f$.
100 * 3. Stabilize \f$u^{j+1}\f$ by projecting onto a norm ball followed by taking a convex combination
101 * with a core vector of Lagrangian multipliers.
102 * 4. Generate GMI cuts based on the optimal simplex tableau.
103 * 5. Relax the newly generated cuts by penalizing and adding them to the objective function.
104 * 6. Go to the next iteration \f$j+1\f$.
105 * 2. Gather all the generated cuts and build an LP by adding all these cuts to the node relaxation.
106 * 3. Solve this LP to obtain its optimal primal and dual solutions.
107 * 4. If this primal solution is MIP primal feasible, then add this solution to the solution pool, add all
108 * the generated cuts to the cutpool or sepastore as needed, and exit the separator.
109 * 5. Otherwise, update the Lagrangian multipliers based on this optimal dual solution, and go to the next
110 * iteration \f$i+1\f$.
111 *
112 * @todo store all LP sols in a data structure, and send them to fix-and-propagate at the end.
113 *
114 * @todo test heuristics such as feasibility pump with multiple input solutions.
115 *
116 * @todo find dual degenerate problems and test the separator on these problems.
117 *
118 * @todo identify instance classes where these cuts work better.
119 *
120 * @todo add termination criteria based on failed efforts.
121 *
122 * @todo for warm starting, if there are additional rows/cols, set their basis status to non-basic and then set WS info.
123 *
124 * @todo filter cuts using multiple explored LP solutions.
125 *
126 * @todo for bases on optimal face only, aggregate to get a new basis and separate it.
127 *
128 * @todo generate other separators in addition to GMI cuts (0-1/2).
129 *
130 * @todo convert iters from int to SCIP_Longint.
131 */
132
133/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
134
135#include "scip/heur_trysol.h"
136#include "scip/sepa_lagromory.h"
137
138#define SEPA_NAME "lagromory"
139#define SEPA_DESC "separator for Lagromory cuts for MIP relaxations"
140#define SEPA_PRIORITY -8000
141#define SEPA_FREQ -1
142#define SEPA_MAXBOUNDDIST 1.0
143#define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
144#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
145
146/* generic parameters */
147#define DEFAULT_AWAY 0.01 /**< minimal integrality violation of a basis variable to try separation */
148#define DEFAULT_DELAYEDCUTS FALSE /**< should cuts be added to the delayed cut pool? */
149#define DEFAULT_SEPARATEROWS TRUE /**< separate rows with integral slack? */
150#define DEFAULT_SORTCUTOFFSOL TRUE /**< sort fractional integer columns based on fractionality? */
151#define DEFAULT_SIDETYPEBASIS TRUE /**< choose side types of row (lhs/rhs) based on basis information? */
152#define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
153#define DEFAULT_MAKEINTEGRAL FALSE /**< try to scale all cuts to integral coefficients? */
154#define DEFAULT_FORCECUTS FALSE /**< force cuts to be added to the LP? */
155#define DEFAULT_ALLOWLOCAL FALSE /**< should locally valid cuts be generated? */
156
157/* parameters related to the separator's termination check */
158#define DEFAULT_MAXROUNDSROOT 1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
159#define DEFAULT_MAXROUNDS 1 /**< maximal number of separation rounds per node (-1: unlimited) */
160#define DEFAULT_DUALDEGENERACYRATETHRESHOLD 0.5 /**< minimum dual degeneracy rate for separator execution */
161#define DEFAULT_VARCONSRATIOTHRESHOLD 1.0 /**< minimum variable-constraint ratio on optimal face for separator execution */
162#define DEFAULT_MINRESTART 1 /**< minimum restart round for separator execution (0: from beginning of the
163 * instance solving, >= n with n >= 1: from restart round n) */
164#define DEFAULT_PERLPMAXCUTSROOT 50 /**< maximal number of cuts separated per Lagromory LP in the root node */
165#define DEFAULT_PERLPMAXCUTS 10 /**< maximal number of cuts separated per Lagromory LP in the non-root node */
166#define DEFAULT_PERROUNDLPITERLIMITFACTOR -1.0 /**< factor w.r.t. root node LP iterations for maximal separating LP iterations
167 * per separation round (negative for no limit) */
168#define DEFAULT_ROOTLPITERLIMITFACTOR -1.0 /**< factor w.r.t. root node LP iterations for maximal separating LP iterations
169 * in the root node (negative for no limit) */
170#define DEFAULT_TOTALLPITERLIMITFACTOR -1.0 /**< factor w.r.t. root node LP iterations for maximal separating LP iterations
171 * in the tree (negative for no limit) */
172#define DEFAULT_PERROUNDMAXLPITERS 50000 /**< maximal number of separating LP iterations per separation round (-1: unlimited) */
173#define DEFAULT_PERROUNDCUTSFACTORROOT 1.0 /**< factor w.r.t. number of integer columns for number of cuts separated per
174 * separation round in root node */
175#define DEFAULT_PERROUNDCUTSFACTOR 0.5 /**< factor w.r.t. number of integer columns for number of cuts separated per
176 * separation round at a non-root node */
177#define DEFAULT_TOTALCUTSFACTOR 50.0 /**< factor w.r.t. number of integer columns for total number of cuts separated */
178#define DEFAULT_MAXMAINITERS 4 /**< maximal number of main loop iterations of the relax-and-cut algorithm */
179#define DEFAULT_MAXSUBGRADIENTITERS 6 /**< maximal number of subgradient loop iterations of the relax-and-cut algorithm */
180
181/* parameters related to the relax-and-cut algorithm */
182#define DEFAULT_MUPARAMCONST TRUE /**< is the mu parameter (factor for step length) constant? */
183#define DEFAULT_MUPARAMINIT 0.01 /**< initial value of the mu parameter (factor for step length) */
184#define DEFAULT_MUPARAMLB 0.0 /**< lower bound for the mu parameter (factor for step length) */
185#define DEFAULT_MUPARAMUB 2.0 /**< upper bound for the mu parameter (factor for step length) */
186#define DEFAULT_MUBACKTRACKFACTOR 0.5 /**< factor of mu while backtracking the mu parameter (factor for step length) -
187 * see updateMuSteplengthParam() */
188#define DEFAULT_MUSLAB1FACTOR 10.0 /**< factor of mu parameter (factor for step length) for larger increment - see
189 * updateMuSteplengthParam() */
190#define DEFAULT_MUSLAB2FACTOR 2.0 /**< factor of mu parameter (factor for step length) for smaller increment - see
191 * updateMuSteplengthParam() */
192#define DEFAULT_MUSLAB3FACTOR 0.5 /**< factor of mu parameter (factor for step length) for reduction - see
193 * updateMuSteplengthParam() */
194#define DEFAULT_DELTASLAB1UB 0.001 /**< factor of delta deciding larger increment of mu parameter (factor for step
195 * length) - see updateMuSteplengthParam() */
196#define DEFAULT_DELTASLAB2UB 0.01 /**< factor of delta deciding smaller increment of mu parameter (factor for step
197 * length) - see updateMuSteplengthParam() */
198#define DEFAULT_UBPARAMPOSFACTOR 2.0 /**< factor for positive upper bound used as an estimate for the optimal
199 * Lagrangian dual value */
200#define DEFAULT_UBPARAMNEGFACTOR 0.5 /**< factor for negative upper bound used as an estimate for the optimal
201 * Lagrangian dual value */
202#define DEFAULT_MAXLAGRANGIANVALSFORAVG 2 /**< maximal number of iterations for rolling average of Lagrangian value */
203#define DEFAULT_MAXCONSECITERSFORMUUPDATE 10 /**< consecutive number of iterations used to determine if mu needs to be backtracked */
204#define DEFAULT_PERROOTLPITERFACTOR 0.2 /**< factor w.r.t. root node LP iterations for iteration limit of each separating
205 * LP (negative for no limit) */
206#define DEFAULT_PERLPITERFACTOR 0.1 /**< factor w.r.t. non-root node LP iterations for iteration limit of each
207 * separating LP (negative for no limit) */
208#define DEFAULT_CUTGENFREQ 1 /**< frequency of subgradient iterations for generating cuts */
209#define DEFAULT_CUTADDFREQ 1 /**< frequency of subgradient iterations for adding cuts to objective function */
210#define DEFAULT_CUTSFILTERFACTOR 1.0 /**< fraction of generated cuts per explored basis to accept from separator */
211#define DEFAULT_OPTIMALFACEPRIORITY 2 /**< priority of the optimal face for separator execution (0: low priority, 1:
212 * medium priority, 2: high priority) */
213#define DEFAULT_AGGREGATECUTS TRUE /**< aggregate all generated cuts using the Lagrangian multipliers? */
214
215/* parameters for stabilization of the Lagrangian multipliers */
216#define DEFAULT_PROJECTIONTYPE 2 /**< the ball into which the Lagrangian multipliers are projected for
217 * stabilization (0: no projection, 1: L1-norm ball projection, 2: L2-norm ball
218 * projection, 3: L_inf-norm ball projection) */
219#define DEFAULT_STABILITYCENTERTYPE 1 /**< type of stability center for taking weighted average of Lagrangian multipliers for
220 * stabilization (0: no weighted stabilization, 1: best Lagrangian multipliers) */
221#define DEFAULT_RADIUSINIT 0.5 /**< initial radius of the ball used in stabilization of Lagrangian multipliers */
222#define DEFAULT_RADIUSMAX 20.0 /**< maximum radius of the ball used in stabilization of Lagrangian multipliers */
223#define DEFAULT_RADIUSMIN 1e-6 /**< minimum radius of the ball used in stabilization of Lagrangian multipliers */
224#define DEFAULT_CONST 2.0 /**< a constant for stablity center based stabilization of Lagrangian multipliers */
225#define DEFAULT_RADIUSUPDATEWEIGHT 0.98 /**< multiplier to evaluate cut violation score used for updating ball radius */
226
227/* macros that are used directly */
228#define RANDSEED 42 /**< random seed */
229#define MAKECONTINTEGRAL FALSE /**< convert continuous variable to integral variables in SCIPmakeRowIntegral()? */
230#define POSTPROCESS TRUE /**< apply postprocessing after MIR calculation? - see SCIPcalcMIR() */
231#define BOUNDSWITCH 0.9999 /**< threshold for bound switching - see SCIPcalcMIR() */
232#define USEVBDS TRUE /**< use variable bounds? - see SCIPcalcMIR() */
233#define FIXINTEGRALRHS FALSE /**< try to generate an integral rhs? - see SCIPcalcMIR() */
234#define MAXAGGRLEN(ncols) (0.1*(ncols)+1000) /**< maximal length of base inequality */
235
236/*
237 * Data structures
238 */
239
240/** separator data */
241struct SCIP_SepaData
242{
243 /* generic variables */
244 SCIP_Real away; /**< minimal integrality violation of a basis variable to try separation */
245 SCIP_Bool delayedcuts; /**< should cuts be added to the delayed cut pool? */
246 SCIP_Bool separaterows; /**< separate rows with integral slack? */
247 SCIP_Bool sortcutoffsol; /**< sort fractional integer columns based on fractionality? */
248 SCIP_Bool sidetypebasis; /**< choose side types of row (lhs/rhs) based on basis information? */
249 SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
250 SCIP_Bool makeintegral; /**< try to scale all cuts to integral coefficients? */
251 SCIP_Bool forcecuts; /**< force cuts to be added to the LP? */
252 SCIP_Bool allowlocal; /**< should locally valid cuts be generated? */
253 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
254 SCIP_HEUR* heurtrysol; /**< a pointer to the trysol heuristic, if available */
255
256 /* used to define separating LPs */
257 SCIP_LPI* lpiwithsoftcuts; /**< pointer to the lpi interface of Lagrangian dual with fixed multipliers */
258 SCIP_LPI* lpiwithhardcuts; /**< pointer to the lpi interface of LP with all generated cuts */
259 int nrowsinhardcutslp; /**< nrows of \a lpiwithhardcuts */
260 int nrunsinsoftcutslp; /**< number of branch-and-bound runs on current instance */
261
262 /* used for termination checks */
263 SCIP_Longint ncalls; /**< number of calls to the separator */
264 int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: unlimited) */
265 int maxrounds; /**< maximal number of separation rounds per node (-1: unlimited) */
266 SCIP_Real dualdegeneracyratethreshold; /**< minimum dual degeneracy rate for separator execution */
267 SCIP_Real varconsratiothreshold; /**< minimum variable-constraint ratio on optimal face for separator execution */
268 int minrestart; /**< minimum restart round for separator execution (0: from beginning of the instance
269 * solving, >= n with n >= 1: from restart round n) */
270 int nmaxcutsperlproot; /**< maximal number of cuts separated per Lagromory LP in the root node */
271 int nmaxcutsperlp; /**< maximal number of cuts separated per Lagromory LP in the non-root node */
272 SCIP_Real perroundlpiterlimitfactor; /**< factor w.r.t. root node LP iterations for maximal separating LP iterations per
273 * separation round (negative for no limit) */
274 SCIP_Real rootlpiterlimitfactor; /**< factor w.r.t. root node LP iterations for maximal separating LP iterations in the
275 * root node (negative for no limit) */
276 SCIP_Real totallpiterlimitfactor; /**< factor w.r.t. root node LP iterations for maximal separating LP iterations in the
277 * tree (negative for no limit) */
278 int perroundnmaxlpiters; /**< maximal number of separating LP iterations per separation round (-1: unlimited) */
279 SCIP_Real perroundcutsfactorroot; /**< factor w.r.t. number of integer columns for number of cuts separated per
280 * separation round in root node */
281 SCIP_Real perroundcutsfactor; /**< factor w.r.t. number of integer columns for number of cuts separated per
282 * separation round at a non-root node */
283 SCIP_Real totalcutsfactor; /**< factor w.r.t. number of integer columns for total number of cuts separated */
284 int nmaxmainiters; /**< maximal number of main loop iterations of the relax-and-cut algorithm */
285 int nmaxsubgradientiters; /**< maximal number of subgradient loop iterations of the relax-and-cut algorithm */
286 int nmaxperroundlpiters; /**< maximal number of separating LP iterations per separation round */
287 int nmaxrootlpiters; /**< maximal number of separating LP iterations in the root node */
288 int nrootlpiters; /**< number of separating LP iterations in the root node */
289 int nmaxtotallpiters; /**< maximal number of separating LP iterations in the tree */
290 int ntotallpiters; /**< number of separating LP iterations in the tree */
291 int nmaxperroundcutsroot; /**< maximal number of cuts separated per separation round in root node */
292 int nmaxperroundcuts; /**< maximal number of cuts separated per separation round */
293 int nmaxtotalcuts; /**< maximal number of cuts separated in the tree */
294 int ntotalcuts; /**< number of cuts separated in the tree */
295
296 /* used for the relax-and-cut algorithm */
297 SCIP_Bool muparamconst; /**< is the mu parameter (factor for step length) constant? */
298 SCIP_Real muparaminit; /**< initial value of the mu parameter (factor for step length) */
299 SCIP_Real muparamlb; /**< lower bound for the mu parameter (factor for step length) */
300 SCIP_Real muparamub; /**< upper bound for the mu parameter (factor for step length) */
301 SCIP_Real mubacktrackfactor; /**< factor of mu while backtracking the mu parameter (factor for step length) - see
302 * updateMuSteplengthParam() */
303 SCIP_Real muslab1factor; /**< factor of mu parameter (factor for step length) for larger increment - see
304 * updateMuSteplengthParam() */
305 SCIP_Real muslab2factor; /**< factor of mu parameter (factor for step length) for smaller increment - see
306 * updateMuSteplengthParam() */
307 SCIP_Real muslab3factor; /**< factor of mu parameter (factor for step length) for reduction - see updateMuSteplengthParam() */
308 SCIP_Real deltaslab1ub; /**< factor of delta deciding larger increment of mu parameter (factor for step
309 * length) - see updateMuSteplengthParam() */
310 SCIP_Real deltaslab2ub; /**< factor of delta deciding smaller increment of mu parameter (factor for step
311 * length) - see updateMuSteplengthParam() */
312 SCIP_Real ubparamposfactor; /**< factor for positive upper bound used as an estimate for the optimal Lagrangian
313 * dual value */
314 SCIP_Real ubparamnegfactor; /**< factor for negative upper bound used as an estimate for the optimal Lagrangian
315 * dual value */
316 int nmaxlagrangianvalsforavg; /**< maximal number of iterations for rolling average of Lagrangian value */
317 int nmaxconsecitersformuupdate; /**< consecutive number of iterations used to determine if mu needs to be backtracked */
318 SCIP_Real perrootlpiterfactor; /**< factor w.r.t. root node LP iterations for iteration limit of each separating LP
319 * (negative for no limit) */
320 SCIP_Real perlpiterfactor; /**< factor w.r.t. non-root node LP iterations for iteration limit of each separating
321 * LP (negative for no limit) */
322 int cutgenfreq; /**< frequency of subgradient iterations for generating cuts */
323 int cutaddfreq; /**< frequency of subgradient iterations for adding cuts to objective function */
324 SCIP_Real cutsfilterfactor; /**< fraction of generated cuts per explored basis to accept from separator */
325 int optimalfacepriority; /**< priority of the optimal face for separator execution (0: low priority, 1: medium
326 * priority, 2: high priority) */
327 SCIP_Bool aggregatecuts; /**< aggregate all generated cuts using the Lagrangian multipliers? */
328
329 /* for stabilization of Lagrangian multipliers */
330 int projectiontype; /**< the ball into which the Lagrangian multipliers are projected for stabilization
331 * (0: no projection, 1: L1-norm ball projection, 2: L2-norm ball projection, 3:
332 * L_inf-norm ball projection) */
333 int stabilitycentertype; /**< type of stability center for taking weighted average of Lagrangian multipliers for
334 * stabilization (0: no weighted stabilization, 1: best Lagrangian multipliers) */
335 SCIP_Real radiusinit; /**< initial radius of the ball used in stabilization of Lagrangian multipliers */
336 SCIP_Real radiusmax; /**< maximum radius of the ball used in stabilization of Lagrangian multipliers */
337 SCIP_Real radiusmin; /**< minimum radius of the ball used in stabilization of Lagrangian multipliers */
338 SCIP_Real constant; /**< a constant for stablity center based stabilization of Lagrangian multipliers */
339 SCIP_Real radiusupdateweight; /**< multiplier to evaluate cut violation score used for updating ball radius */
340};
341
342
343/*
344 * Local methods
345 */
346
347/** start the diving mode for solving LPs corresponding to the Lagrangian dual with fixed multipliers in the subgradient
348 * loop of the separator, and update some sepadata values */
349static
350SCIP_RETCODE createLPWithSoftCuts(
351 SCIP* scip, /**< SCIP data structure */
352 SCIP_SEPADATA* sepadata /**< separator data structure */
353 )
354{
355 SCIP_ROW** rows;
356 SCIP_COL** cols;
357 int nruns;
358 int runnum;
359 int nrows;
360 int ncols;
361 unsigned int nintcols;
362 SCIP_Longint nrootlpiters;
363 int i;
364
365 assert(scip != NULL);
366 assert(sepadata != NULL);
367
368 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
369 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
370 runnum = SCIPgetNRuns(scip); /* current run number of SCIP (starts from 1) indicating restarts */
371 nruns = sepadata->nrunsinsoftcutslp; /* previous run number of SCIP in which the diving LP was created */
372 nintcols = 0;
373
374 /* start diving mode so that the diving LP can be used for all subgradient iterations */
375 SCIP_CALL( SCIPstartDive(scip) );
376
377 /* store LPI pointer to be able to use LPI functions directly (e.g., setting time limit) */
378 SCIP_CALL( SCIPgetLPI(scip, &(sepadata->lpiwithsoftcuts)) );
379
380 /* if called for the first time in a restart (including the initial run), set certain sepadata values */
381 if( nruns != runnum )
382 {
383 /* get number of LP iterations of root node's first LP solving */
384 nrootlpiters = SCIPgetNRootFirstLPIterations(scip);
385
386 /* calculate maximum number of LP iterations allowed for all separation calls in the root node */
387 if( (sepadata->rootlpiterlimitfactor >= 0.0) && !SCIPisInfinity(scip, sepadata->rootlpiterlimitfactor) )
388 sepadata->nmaxrootlpiters = (int)(sepadata->rootlpiterlimitfactor * nrootlpiters);
389 else
390 sepadata->nmaxrootlpiters = -1; /* no finite limit */
391
392 /* calculate maximum number of LP iterations allowed for all separation calls in the entire tree */
393 if( (sepadata->totallpiterlimitfactor >= 0.0) && !SCIPisInfinity(scip, sepadata->totallpiterlimitfactor) )
394 sepadata->nmaxtotallpiters = (int)(sepadata->totallpiterlimitfactor * nrootlpiters);
395 else
396 sepadata->nmaxtotallpiters = -1; /* no finite limit */
397
398 /* calculate maximum number of LP iterations allowed per separation call */
399 if( (sepadata->perroundlpiterlimitfactor >= 0.0) && !SCIPisInfinity(scip, sepadata->perroundlpiterlimitfactor) )
400 sepadata->nmaxperroundlpiters = (int)(sepadata->perroundlpiterlimitfactor * nrootlpiters);
401 else
402 sepadata->nmaxperroundlpiters = -1; /* no finite limit */
403
404 /* update maximum number of LP iterations allowed per separation call using absolute limits */
405 if( sepadata->perroundnmaxlpiters > 0 )
406 sepadata->nmaxperroundlpiters = ((sepadata->nmaxperroundlpiters >= 0) ? MIN(sepadata->nmaxperroundlpiters,
407 sepadata->perroundnmaxlpiters) : sepadata->perroundnmaxlpiters);
408
409 /* set maximum number of cuts allowed to generate per round in root and non-root nodes as well as the total tree */
410 for( i = 0; i < ncols; ++i )
411 nintcols += SCIPcolIsIntegral(cols[i]);
412
413 sepadata->nmaxperroundcutsroot = (int)(sepadata->perroundcutsfactorroot * nintcols);
414 sepadata->nmaxperroundcuts = (int)(sepadata->perroundcutsfactor * nintcols);
415
416 if( sepadata->ncalls == 0 )
417 {
418 sepadata->nmaxtotalcuts = (int)(sepadata->totalcutsfactor * nintcols);
419 sepadata->ntotalcuts = 0;
420 }
421
422 /* update the run number of solving to represent the restart number in which the above limits were set */
423 sepadata->nrunsinsoftcutslp = runnum;
424 }
425
426 return SCIP_OKAY;
427}
428
429/** end the diving mode that was used for solving LPs corresponding to the Lagrangian dual with fixed multipliers */
430static
431SCIP_RETCODE deleteLPWithSoftCuts(
432 SCIP* scip, /**< SCIP data structure */
433 SCIP_SEPADATA* sepadata /**< separator data structure */
434 )
435{
436 assert(scip != NULL);
437 assert(sepadata != NULL);
438
439 SCIP_CALL( SCIPendDive(scip) );
440
441 return SCIP_OKAY;
442}
443
444/** set up LP interface to solve LPs in the (outer) main loop of the relax-and-cut algorithm; these LPs are built by
445 * adding all the generated cuts to the node relaxation */
446/* @todo add lpi iters to global statistics */
447static
448SCIP_RETCODE createLPWithHardCuts(
449 SCIP* scip, /**< SCIP data structure */
450 SCIP_SEPADATA* sepadata, /**< separator data structure */
451 SCIP_ROW** cuts, /**< generated cuts to be added to the LP */
452 int ncuts /**< number of generated cuts to be added to the LP */
453 )
454{
455 SCIP_ROW** rows;
456 SCIP_COL** cols;
457 SCIP_Real* collb;
458 SCIP_Real* colub;
459 SCIP_Real* colobj;
460 SCIP_Real* rowlhs;
461 SCIP_Real* rowrhs;
462 SCIP_Real rowconst;
463 SCIP_Real* rowvals;
464 SCIP_Real* rowval;
465 SCIP_COL** rowcols;
466 SCIP_LPI* wslpi;
467 SCIP_LPISTATE* lpistate;
468 BMS_BLKMEM* blkmem;
469 SCIP_Real pinf;
470 SCIP_Real ninf;
471 int nrows;
472 int ncols;
473 int nrownonz;
474 int collppos;
475 int* rowcolinds;
476 int* rowbegs;
477 int i;
478 int j;
479
480 assert(scip != NULL);
481 assert(sepadata != NULL);
482
483 SCIP_LPI** lpi = &(sepadata->lpiwithhardcuts);
484 blkmem = SCIPblkmem(scip);
485
486 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
487 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
488
489 /* if this function is called for the first time in this separation round, then create an LPI and add cols & rows */
490 if( ncuts == 0 )
491 {
492 if( *lpi != NULL )
493 {
494 SCIP_CALL( SCIPlpiFree(lpi) );
495 *lpi = NULL;
496 }
497 assert(*lpi == NULL);
498
499 /* create an LPI */
500 SCIP_CALL( SCIPlpiCreate(lpi, SCIPgetMessagehdlr(scip), "node LP with generated cuts", SCIP_OBJSEN_MINIMIZE) );
501
502 /* add cols to the LP interface */
503 SCIP_CALL( SCIPallocBufferArray(scip, &colobj, ncols) );
504 SCIP_CALL( SCIPallocBufferArray(scip, &collb, ncols) );
505 SCIP_CALL( SCIPallocBufferArray(scip, &colub, ncols) );
506
507 /* gather required column information */
508 for( i = 0; i < ncols; ++i )
509 {
510 colobj[i] = SCIPcolGetObj(cols[i]);
511 collb[i] = SCIPcolGetLb(cols[i]);
512 colub[i] = SCIPcolGetUb(cols[i]);
513 }
514 /* add cols */
515 SCIP_CALL( SCIPlpiAddCols(*lpi, ncols, colobj, collb, colub, NULL, 0, NULL, NULL, NULL) );
516 SCIPfreeBufferArray(scip, &colub);
517 SCIPfreeBufferArray(scip, &collb);
518 SCIPfreeBufferArray(scip, &colobj);
519
520 /* add rows to the LP interface */
521 /* find number of nonzeroes in rows */
522 nrownonz = 0;
523 for( i = 0; i < nrows; ++i )
524 {
525 assert(!(SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) && SCIPisInfinity(scip, SCIProwGetRhs(rows[i]))));
526 nrownonz += SCIProwGetNLPNonz(rows[i]);
527 }
528 SCIP_CALL( SCIPallocBufferArray(scip, &rowcolinds, nrownonz) );
529 SCIP_CALL( SCIPallocBufferArray(scip, &rowvals, nrownonz) );
530 SCIP_CALL( SCIPallocBufferArray(scip, &rowbegs, nrows + 1) );
531 SCIP_CALL( SCIPallocBufferArray(scip, &rowlhs, nrows) );
532 SCIP_CALL( SCIPallocBufferArray(scip, &rowrhs, nrows) );
533
534 /* gather required row information */
535 rowbegs[0] = 0;
536 pinf = SCIPlpiInfinity(*lpi);
537 ninf = -SCIPlpiInfinity(*lpi);
538 for( i = 0; i < nrows; ++i )
539 {
540 nrownonz = SCIProwGetNLPNonz(rows[i]);
541 assert(nrownonz <= ncols);
542 rowval = SCIProwGetVals(rows[i]);
543 rowcols = SCIProwGetCols(rows[i]);
544
545 rowbegs[i + 1] = rowbegs[i] + nrownonz;
546 rowconst = SCIProwGetConstant(rows[i]);
547 rowlhs[i] = SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) ? ninf : SCIProwGetLhs(rows[i]) - rowconst;
548 rowrhs[i] = SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) ? pinf : SCIProwGetRhs(rows[i]) - rowconst;
549
550 for( j = 0; j < nrownonz; ++j )
551 {
552 collppos = SCIPcolGetLPPos(rowcols[j]);
553 assert(collppos >= 0);
554 assert(collppos <= ncols);
555
556 rowcolinds[rowbegs[i] + j] = collppos;
557 rowvals[rowbegs[i] + j] = rowval[j];
558 }
559 }
560
561 /* add rows */
562 SCIP_CALL( SCIPlpiAddRows(*lpi, nrows, rowlhs, rowrhs, NULL, rowbegs[nrows], rowbegs, rowcolinds, rowvals) );
563
564 /* get warm starting info */
565 SCIP_CALL( SCIPgetLPI(scip, &wslpi) );
566 SCIP_CALL( SCIPlpiGetState(wslpi, blkmem, &lpistate) );
567 }
568 /* if there are any cuts, then add the cuts that were not added earlier to the LPI */
569 else
570 {
571 assert(nrows + ncuts >= sepadata->nrowsinhardcutslp);
572
573 /* get warm starting info */
574 wslpi = *lpi;
575 SCIP_CALL( SCIPlpiGetState(wslpi, blkmem, &lpistate) );
576
577 /* find number of nonzeros in cuts and allocate memory */
578 nrownonz = 0;
579 pinf = SCIPlpiInfinity(*lpi);
580 ninf = -SCIPlpiInfinity(*lpi);
581
582 for( i = sepadata->nrowsinhardcutslp - nrows; i < ncuts; ++i )
583 {
584 assert(!(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])) && SCIPisInfinity(scip, SCIProwGetRhs(cuts[i]))));
585 assert(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])));
586 assert(!SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])));
587 nrownonz += SCIProwGetNNonz(cuts[i]);
588 }
589 SCIP_CALL( SCIPallocBufferArray(scip, &rowcolinds, nrownonz) );
590 SCIP_CALL( SCIPallocBufferArray(scip, &rowvals, nrownonz) );
591 SCIP_CALL( SCIPallocBufferArray(scip, &rowbegs, (ncuts - sepadata->nrowsinhardcutslp + nrows) + 1) );
592 SCIP_CALL( SCIPallocBufferArray(scip, &rowlhs, (ncuts - sepadata->nrowsinhardcutslp + nrows)) );
593 SCIP_CALL( SCIPallocBufferArray(scip, &rowrhs, (ncuts - sepadata->nrowsinhardcutslp + nrows)) );
594
595 /* gather required cut information */
596 rowbegs[0] = 0;
597 for( i = sepadata->nrowsinhardcutslp - nrows; i < ncuts; ++i )
598 {
599 nrownonz = SCIProwGetNNonz(cuts[i]);
600 assert(nrownonz <= ncols);
601 rowval = SCIProwGetVals(cuts[i]);
602 rowcols = SCIProwGetCols(cuts[i]);
603
604 rowbegs[i - sepadata->nrowsinhardcutslp + nrows + 1] = rowbegs[i - sepadata->nrowsinhardcutslp + nrows] +
605 nrownonz;
606 rowconst = SCIProwGetConstant(cuts[i]);
607 rowlhs[i - sepadata->nrowsinhardcutslp + nrows] = SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])) ? ninf :
608 SCIProwGetLhs(cuts[i]) - rowconst;
609 rowrhs[i - sepadata->nrowsinhardcutslp + nrows] = SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])) ? pinf :
610 SCIProwGetRhs(cuts[i]) - rowconst;
611
612 for( j = 0; j < nrownonz; ++j )
613 {
614 collppos = SCIPcolGetLPPos(rowcols[j]);
615 assert(collppos >= 0);
616 assert(collppos <= ncols);
617
618 rowcolinds[rowbegs[i - sepadata->nrowsinhardcutslp + nrows] + j] = collppos;
619 rowvals[rowbegs[i - sepadata->nrowsinhardcutslp + nrows] + j] = rowval[j];
620 }
621 }
622
623 /* add cuts */
624 SCIP_CALL( SCIPlpiAddRows(*lpi, (ncuts - sepadata->nrowsinhardcutslp + nrows), rowlhs, rowrhs, NULL,
625 rowbegs[(ncuts - sepadata->nrowsinhardcutslp + nrows)], rowbegs, rowcolinds, rowvals) );
626 }
627
628 /* set warm starting basis */
629 SCIP_CALL( SCIPlpiSetState(*lpi, blkmem, lpistate) );
630
631 /* reset remaining sepadata values */
632 sepadata->nrowsinhardcutslp = nrows + ncuts;
633
634 /* free memory */
635 SCIP_CALL( SCIPlpiFreeState(*lpi, blkmem, &lpistate) );
636 SCIPfreeBufferArray(scip, &rowrhs);
637 SCIPfreeBufferArray(scip, &rowlhs);
638 SCIPfreeBufferArray(scip, &rowbegs);
639 SCIPfreeBufferArray(scip, &rowvals);
640 SCIPfreeBufferArray(scip, &rowcolinds);
641
642 return SCIP_OKAY;
643}
644
645/** free separator data */
646static
647SCIP_RETCODE sepadataFree(
648 SCIP* scip, /**< SCIP data structure */
649 SCIP_SEPADATA** sepadata /**< separator data structure */
650 )
651{
652 assert(scip != NULL);
653 assert(sepadata != NULL);
654 assert(*sepadata != NULL);
655
656 if( (*sepadata)->lpiwithhardcuts != NULL )
657 {
658 SCIP_CALL( SCIPlpiFree(&((*sepadata)->lpiwithhardcuts)) );
659 }
660
661 (*sepadata)->nrowsinhardcutslp = 0;
662 (*sepadata)->nrunsinsoftcutslp = 0;
663 (*sepadata)->ncalls = 0;
664 (*sepadata)->nmaxperroundlpiters = 0;
665 (*sepadata)->nmaxrootlpiters = 0;
666 (*sepadata)->nrootlpiters = 0;
667 (*sepadata)->nmaxtotallpiters = 0;
668 (*sepadata)->ntotallpiters = 0;
669 (*sepadata)->nmaxperroundcutsroot = 0;
670 (*sepadata)->nmaxperroundcuts = 0;
671 (*sepadata)->nmaxtotalcuts = 0;
672 (*sepadata)->ntotalcuts = 0;
673
674 SCIPfreeBlockMemory(scip, sepadata);
675
676 return SCIP_OKAY;
677}
678
679/** update mu parameter which is used as a factor in the step length calculation; refer to the top of the file for a
680 * description of the formula. */
681/* @todo some adaptive strategy like constant after certain changes? */
682static
683SCIP_RETCODE updateMuSteplengthParam(
684 SCIP* scip, /**< SCIP data structure */
685 SCIP_SEPADATA* sepadata, /**< separator data structure */
686 int subgradientiternum, /**< subgradient iteration number */
687 SCIP_Real ubparam, /**< estimate of the optimal Lagrangian dual value */
688 SCIP_Real* lagrangianvals, /**< vector of Lagrangian values found so far */
689 SCIP_Real bestlagrangianval, /**< best Lagrangian value found so far */
690 SCIP_Real avglagrangianval, /**< rolling average of the Lagrangian values found so far */
691 SCIP_Real* muparam, /**< mu parameter to be updated */
692 SCIP_Bool* backtrack /**< whether mu parameter has been backtracked */
693 )
694{
695 SCIP_Real delta;
696 SCIP_Real deltaslab1ub;
697 SCIP_Real deltaslab2ub;
698 SCIP_Real muslab1factor;
699 SCIP_Real muslab2factor;
700 SCIP_Real muslab3factor;
701 int maxiters;
702 int i;
703
704 assert( backtrack != NULL );
705
706 *backtrack = FALSE;
707
708 /* update the mu parameter only if it is not set to be a constant value */
709 if( !sepadata->muparamconst )
710 {
711 delta = ubparam - bestlagrangianval;
712 deltaslab1ub = MIN(sepadata->deltaslab1ub, sepadata->deltaslab2ub);
713 deltaslab2ub = MAX(sepadata->deltaslab1ub, sepadata->deltaslab2ub);
714
715 /* ensure that the ordering of different user input parameters is as expected */
716 if( SCIPisPositive(scip, sepadata->muslab1factor - sepadata->muslab2factor) )
717 {
718 if( SCIPisPositive(scip, sepadata->muslab2factor - sepadata->muslab3factor) )
719 {
720 muslab1factor = sepadata->muslab1factor;
721 muslab2factor = sepadata->muslab2factor;
722 muslab3factor = sepadata->muslab3factor;
723 }
724 else
725 {
726 if( SCIPisPositive(scip, sepadata->muslab1factor - sepadata->muslab3factor) )
727 {
728 muslab1factor = sepadata->muslab1factor;
729 muslab2factor = sepadata->muslab3factor;
730 muslab3factor = sepadata->muslab2factor;
731 }
732 else
733 {
734 muslab1factor = sepadata->muslab3factor;
735 muslab2factor = sepadata->muslab1factor;
736 muslab3factor = sepadata->muslab2factor;
737 }
738 }
739 }
740 else
741 {
742 if( SCIPisPositive(scip, sepadata->muslab1factor - sepadata->muslab3factor) )
743 {
744 muslab1factor = sepadata->muslab2factor;
745 muslab2factor = sepadata->muslab1factor;
746 muslab3factor = sepadata->muslab3factor;
747 }
748 else
749 {
750 if( SCIPisPositive(scip, sepadata->muslab2factor - sepadata->muslab3factor) )
751 {
752 muslab1factor = sepadata->muslab2factor;
753 muslab2factor = sepadata->muslab3factor;
754 muslab3factor = sepadata->muslab1factor;
755 }
756 else
757 {
758 muslab1factor = sepadata->muslab3factor;
759 muslab2factor = sepadata->muslab2factor;
760 muslab3factor = sepadata->muslab1factor;
761 }
762 }
763 }
764
765 maxiters = MIN(sepadata->nmaxconsecitersformuupdate, sepadata->nmaxlagrangianvalsforavg);
766 i = -1;
767
768 /* if certain number of iterations are done, then check for a possibility of backtracking and apply accordingly */
769 if( subgradientiternum >= maxiters )
770 {
771 for( i = subgradientiternum - maxiters; i < subgradientiternum; i++ )
772 {
773 if( SCIPisGE(scip, lagrangianvals[i], bestlagrangianval - delta) )
774 break;
775 }
776
777 if( i == subgradientiternum )
778 {
779 *muparam *= sepadata->mubacktrackfactor;
780 *backtrack = TRUE;
781 }
782 }
783
784 /* update mu parameter based on the different between best and average Lagrangian values */
785 if( (subgradientiternum < maxiters) || (i >= 0 && i < subgradientiternum) )
786 {
787 if( bestlagrangianval - avglagrangianval < deltaslab1ub * delta )
788 *muparam *= muslab1factor;
789 else if( bestlagrangianval - avglagrangianval < deltaslab2ub * delta )
790 *muparam *= muslab2factor;
791 else
792 *muparam *= muslab3factor;
793 }
794
795 /* reset the mu parameter to within its bounds */
796 *muparam = MAX(*muparam, sepadata->muparamlb);
797 *muparam = MIN(*muparam, sepadata->muparamub);
798 }
799
800 return SCIP_OKAY;
801}
802
803/** update subgradient, i.e., residuals of generated cuts
804 * @note assuming that \f$i^{th}\f$ cut is of the form \f${\alpha^i}^T x \leq {\alpha^i_0}\f$.
805 */
806static
807void updateSubgradient(
808 SCIP* scip, /**< SCIP data structure */
809 SCIP_SOL* sol, /**< LP solution used in updating subgradient vector */
810 SCIP_ROW** cuts, /**< cuts generated so far */
811 int ncuts, /**< number of cuts generated so far */
812 SCIP_Real* subgradient, /**< vector of subgradients to be updated */
813 SCIP_Real* dualvector, /**< Lagrangian multipliers */
814 SCIP_Bool* subgradientzero, /**< whether the subgradient vector is all zero */
815 int* ncutviols, /**< number of violations of generated cuts */
816 SCIP_Real* maxcutviol, /**< maximum violation of generated cuts */
817 int* nnzsubgradientdualprod, /**< number of nonzero products of subgradient vector and Lagrangian multipliers (i.e.,
818 * number of complementarity slackness violations) */
819 SCIP_Real* maxnzsubgradientdualprod /**< maximum value of nonzero products of subgradient vector and Lagrangian multipliers
820 * (i.e., maximum value of complementarity slackness violations) */
821 )
822{
823 int nzerosubgradient;
824 SCIP_Real term;
825 int i;
826
827 assert(subgradientzero != NULL);
828 assert(ncutviols != NULL);
829 assert(maxcutviol != NULL);
830 assert(nnzsubgradientdualprod != NULL);
831 assert(maxnzsubgradientdualprod != NULL);
832
833 *ncutviols = 0;
834 *maxcutviol = 0.0;
835 *nnzsubgradientdualprod = 0;
836 *maxnzsubgradientdualprod = 0.0;
837 nzerosubgradient = 0;
838 *subgradientzero = FALSE;
839
840 /* for each cut, calculate the residual along with various violation metrics */
841 for( i = 0; i < ncuts; i++ )
842 {
843 assert(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])));
844 assert(!SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])));
845 subgradient[i] = SCIPgetRowSolActivity(scip, cuts[i], sol) + SCIProwGetConstant(cuts[i]) - SCIProwGetRhs(cuts[i]);
846
847 if( SCIPisFeasZero(scip, subgradient[i]) )
848 {
849 subgradient[i] = 0.0;
850 nzerosubgradient++;
851 }
852 else
853 {
854 /* check for cut violation */
855 if( SCIPisFeasPositive(scip, subgradient[i]) )
856 {
857 (*ncutviols)++;
858 *maxcutviol = MAX(*maxcutviol, subgradient[i]);
859 }
860
861 /* check for violation of complementarity slackness associated with the cut */
862 if( !SCIPisZero(scip, subgradient[i] * dualvector[i]) )
863 {
864 (*nnzsubgradientdualprod)++;
865 term = REALABS(subgradient[i] * dualvector[i]);
866 *maxnzsubgradientdualprod = MAX(*maxnzsubgradientdualprod, term);
867 }
868 }
869 }
870
871 /* indicator for all zero subgradient vector */
872 if( nzerosubgradient == ncuts )
873 *subgradientzero = TRUE;
874}
875
876/** update Lagrangian value, i.e., optimal value of the Lagrangian dual with fixed multipliers */
877static
878void updateLagrangianValue(
879 SCIP* scip, /**< SCIP data structure */
880 SCIP_Real objval, /**< objective value of the Lagrangian dual with fixed multipliers */
881 SCIP_Real* dualvector, /**< Lagrangian multipliers */
882 SCIP_ROW** cuts, /**< cuts generated so far */
883 int ncuts, /**< number of cuts generated so far */
884 SCIP_Real* lagrangianval /**< Lagrangian value to be updated */
885 )
886{
887 int i;
888
889 assert(lagrangianval != NULL);
890
891 *lagrangianval = objval;
892
893 for( i = 0; i < ncuts; i++ )
894 {
895 assert(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])));
896 assert(!SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])));
897 *lagrangianval += dualvector[i] * (SCIProwGetConstant(cuts[i]) - SCIProwGetRhs(cuts[i]));
898 }
899}
900
901/** update step length based on various input arguments; refer to the top of the file for an expression */
902static
903void updateStepLength(
904 SCIP* scip, /**< SCIP data structure */
905 SCIP_Real muparam, /**< mu parameter used as a factor for step length */
906 SCIP_Real ubparam, /**< estimate of the optimal Lagrangian dual value */
907 SCIP_Real lagrangianval, /**< Lagrangian value */
908 SCIP_Real* subgradient, /**< subgradient vector */
909 int ncuts, /**< number of cuts generated so far */
910 SCIP_Real* steplength /**< step length to be updated */
911 )
912{
913 SCIP_Real normsquared = 0.0;
914 int i;
915
916 for( i = 0; i < ncuts; i++ )
917 normsquared += SQR(subgradient[i]);
918
919 if( !SCIPisFeasZero(scip, normsquared) )
920 *steplength = (muparam * (ubparam - lagrangianval))/(normsquared); /*lint !e795*/
921}
922
923/** update the ball radius (based on various violation metrics) that is used for stabilization of Lagrangian multipliers */
924static
925void updateBallRadius(
926 SCIP* scip, /**< SCIP data structure */
927 SCIP_SEPADATA* sepadata, /**< separator data structure */
928 SCIP_Real maxviolscore, /**< weighted average of maximum value of generated cut violations and maximum value of
929 * complementarity slackness violations, in the current iteration */
930 SCIP_Real maxviolscoreold, /**< weighted average of maximum value of generated cut violations and maximum value of
931 * complementarity slackness violations, in the previous iteration */
932 SCIP_Real nviolscore, /**< weighted average of number of generated cut violations and number of complementarity
933 * slackness violations, in the current iteration */
934 SCIP_Real nviolscoreold, /**< weighted average of number of generated cut violations and number of complementarity
935 * slackness violations, in the previous iteration */
936 int nlpiters, /**< number of LP iterations taken for solving the Lagrangian dual with fixed multipliers in
937 * current iteration */
938 SCIP_Real* ballradius /**< norm ball radius to be updated */
939 )
940{
941 SCIP_Bool maxviolscoreimproved;
942 SCIP_Bool nviolscoreimproved;
943
944 assert(ballradius != NULL);
945
946 maxviolscoreimproved = !SCIPisNegative(scip, maxviolscoreold - maxviolscore);
947 nviolscoreimproved = !SCIPisNegative(scip, nviolscoreold - nviolscore);
948
949 if( maxviolscoreimproved && nviolscoreimproved )
950 {
951 /* both the maximum violation and number of violations scores have become better, so, increase the radius */
952 if( sepadata->optimalfacepriority <= 1 )
953 {
954 *ballradius *= 2.0;
955 *ballradius = MIN(*ballradius, sepadata->radiusmax);
956 }
957 else
958 {
959 *ballradius *= 1.5;
960 *ballradius = MIN(*ballradius, sepadata->radiusmax/2.0);
961 }
962 }
963 else if( !maxviolscoreimproved && !nviolscoreimproved )
964 {
965 /* both the maximum violation and number of violations scores have become worse, so, decrease the radius */
966 *ballradius *= 0.5;
967 *ballradius = MAX(*ballradius, sepadata->radiusmin);
968 }
969 else if( nlpiters == 0 )
970 {
971 /* only one among the maximum violation and number of violations scores has become better, and the LP basis did
972 * not change (i.e., nlpters = 0), so, increase the radius slightly */
973 if( sepadata->optimalfacepriority <= 1 )
974 {
975 *ballradius *= 1.5;
976 *ballradius = MIN(*ballradius, sepadata->radiusmax);
977 }
978 else
979 {
980 *ballradius *= 1.2;
981 *ballradius = MIN(*ballradius, sepadata->radiusmax/2.0);
982 }
983 }
984}
985
986/** projection of Lagrangian multipliers onto L1-norm ball. This algorithm is based on the following article
987 *
988 * Condat L. (2016).@n
989 * Fast projection onto the simplex and the \f$l_1\f$ ball.@n
990 * Mathematical Programming, 158, 1-2, 575-585.
991 *
992 */
993static
994SCIP_RETCODE l1BallProjection(
995 SCIP* scip, /**< SCIP data structure */
996 SCIP_Real* dualvector, /**< Lagrangian multipliers to be projected onto L1-norm vall */
997 int dualvectorlen, /**< length of the Lagrangian multipliers vector */
998 SCIP_Real radius /**< radius of the L1-norm ball */
999 )
1000{
1001 SCIP_Real* temp1vals;
1002 SCIP_Real* temp2vals;
1003 SCIP_Real pivotparam;
1004 SCIP_Real val;
1005 SCIP_Real term;
1006 SCIP_Bool temp1changed;
1007 int ntemp1removed;
1008 int* temp1inds;
1009 int* temp2inds;
1010 int temp1len;
1011 int temp2len;
1012 int i;
1013 int j;
1014
1015 assert(!SCIPisNegative(scip, radius));
1016 val = REALABS(dualvector[0]);
1017
1018 /* calculate the L1-norm of the Lagrangian multipliers */
1019 for( i = 1; i < dualvectorlen; i++ )
1020 val += REALABS(dualvector[i]);
1021
1022 /* if the vector of Lagrangian multipliers lies outside the L1-norm ball, then do the projection */
1023 if( SCIPisGT(scip, val, radius) )
1024 {
1025 SCIP_CALL( SCIPallocCleanBufferArray(scip, &temp1vals, dualvectorlen) );
1026 SCIP_CALL( SCIPallocCleanBufferArray(scip, &temp2vals, dualvectorlen) );
1027 SCIP_CALL( SCIPallocBufferArray(scip, &temp1inds, dualvectorlen) );
1028 SCIP_CALL( SCIPallocBufferArray(scip, &temp2inds, dualvectorlen) );
1029 for( i = 0; i < dualvectorlen; i++ )
1030 {
1031 temp1inds[i] = -1;
1032 temp2inds[i] = -1;
1033 }
1034 temp2len = 0;
1035
1036 temp1vals[0] = REALABS(dualvector[0]);
1037 temp1inds[0] = 0;
1038 temp1len = 1;
1039 pivotparam = REALABS(dualvector[0]) - radius;
1040
1041 for( i = 1; i < dualvectorlen; i++ )
1042 {
1043 if( SCIPisGT(scip, REALABS(dualvector[i]), pivotparam) )
1044 {
1045 pivotparam += ((REALABS(dualvector[i]) - pivotparam) / (temp1len + 1));
1046 if( SCIPisGT(scip, pivotparam, REALABS(dualvector[i]) - radius) )
1047 {
1048 temp1vals[temp1len] = REALABS(dualvector[i]);
1049 temp1inds[temp1len] = i;
1050 temp1len++;
1051 }
1052 else
1053 {
1054 for( j = 0; j < temp1len; j++ )
1055 {
1056 temp2vals[temp2len + j] = temp1vals[j];
1057 temp2inds[temp2len + j] = temp1inds[j];
1058 }
1059 temp2len += temp1len;
1060 temp1vals[0] = REALABS(dualvector[i]);
1061 temp1inds[0] = i;
1062 temp1len = 1;
1063 pivotparam = REALABS(dualvector[i]) - radius;
1064 }
1065 }
1066 }
1067
1068 for( i = 0; i < temp2len; i++ )
1069 {
1070 if( SCIPisGT(scip, temp2vals[i], pivotparam) )
1071 {
1072 temp1vals[temp1len] = temp2vals[i];
1073 temp1inds[temp1len] = temp2inds[i];
1074 temp1len++;
1075 pivotparam += ((temp2vals[i] - pivotparam) / temp1len);
1076 }
1077 }
1078
1079 temp1changed = TRUE;
1080 ntemp1removed = 0;
1081 while( temp1changed )
1082 {
1083 temp1changed = FALSE;
1084
1085 for( i = 0; i < temp1len; i++ )
1086 {
1087 /* @note the third condition (temp1len - ntemp1removed > 0) is true as long as the first condition
1088 * (temp1inds[i] >= 0) is true.
1089 */
1090 if( (temp1inds[i] >= 0) && SCIPisLE(scip, temp1vals[i], pivotparam) )
1091 {
1092 temp1inds[i] = -1;
1093 temp1changed = TRUE;
1094 ntemp1removed++;
1095 assert(temp1len - ntemp1removed > 0);
1096 /* coverity[divide_by_zero] */
1097 pivotparam += ((pivotparam - temp1vals[i]) / (temp1len - ntemp1removed));
1098 }
1099 }
1100 }
1101
1102 for( i = 0; i < dualvectorlen; i++ )
1103 {
1104 term = REALABS(dualvector[i]);
1105 val = MAX(term - pivotparam, 0.0);
1106
1107 if( SCIPisPositive(scip, dualvector[i]) )
1108 {
1109 dualvector[i] = val;
1110 }
1111 else if( SCIPisNegative(scip, dualvector[i]) )
1112 {
1113 dualvector[i] = -val;
1114 }
1115 }
1116
1117 /* free memory */
1118 for( i = 0; i < dualvectorlen; i++ )
1119 {
1120 temp2vals[i] = 0.0;
1121 temp1vals[i] = 0.0;
1122 }
1123 SCIPfreeBufferArray(scip, &temp2inds);
1124 SCIPfreeBufferArray(scip, &temp1inds);
1125 SCIPfreeCleanBufferArray(scip, &temp2vals);
1126 SCIPfreeCleanBufferArray(scip, &temp1vals);
1127 }
1128
1129 return SCIP_OKAY;
1130}
1131
1132/** projection of Lagrangian multipliers onto L2-norm ball */
1133static
1134void l2BallProjection(
1135 SCIP* scip, /**< SCIP data structure */
1136 SCIP_Real* dualvector, /**< Lagrangian multipliers to be projected onto L2-norm vall */
1137 int dualvectorlen, /**< length of the Lagrangian multipliers vector */
1138 SCIP_Real radius /**< radius of the L2-norm ball */
1139 )
1140{
1141 SCIP_Real l2norm;
1142 SCIP_Real factor;
1143 int i;
1144
1145 assert(!SCIPisNegative(scip, radius));
1146
1147 l2norm = 0.0;
1148
1149 /* calculate the L2-norm of the Lagrangian multipliers */
1150 for( i = 0; i < dualvectorlen; i++ )
1151 l2norm += SQR(dualvector[i]);
1152 l2norm = sqrt(l2norm);
1153 factor = radius/(1.0 + l2norm);
1154
1155 /* if the vector of Lagrangian multipliers is outside the L2-norm ball, then do the projection */
1156 if( SCIPisGT(scip, l2norm, radius) && SCIPisLT(scip, factor, 1.0) )
1157 {
1158 for( i = 0; i < dualvectorlen; i++ )
1159 dualvector[i] *= factor;
1160 }
1161}
1162
1163/** projection of Lagrangian multipliers onto L_infinity-norm ball */
1164static
1165void linfBallProjection(
1166 SCIP* scip, /**< SCIP data structure */
1167 SCIP_Real* dualvector, /**< Lagrangian multipliers to be projected onto L_infinity-norm vall */
1168 int dualvectorlen, /**< length of the Lagrangian multipliers vector */
1169 SCIP_Real radius /**< radius of the L_infinity-norm ball */
1170 )
1171{
1172 int i;
1173
1174 assert(!SCIPisNegative(scip, radius));
1175
1176 /* if the vector of Lagrangian multipliers is outside the L_infinity-norm ball, then do the projection */
1177 for( i = 0; i < dualvectorlen; i++ )
1178 {
1179 if( SCIPisLT(scip, dualvector[i], -radius) )
1180 dualvector[i] = -radius;
1181 else if( SCIPisGT(scip, dualvector[i], radius) )
1182 dualvector[i] = radius;
1183 }
1184}
1185
1186/** weighted Lagrangian multipliers based on a given vector as stability center */
1187/* @todo calculate weight outside this function and pass it (so that this function becomes generic and independent of
1188 * the terminology related to best Lagrangian multipliers)
1189 */
1190static
1191void weightedDualVector(
1192 SCIP_SEPADATA* sepadata, /**< separator data structure */
1193 SCIP_Real* dualvector, /**< Lagrangian multipliers */
1194 int dualvectorlen, /**< length of the Lagrangian multipliers vector */
1195 SCIP_Real* stabilitycenter, /**< stability center (i.e., core vector of Lagrangian multipliers) */
1196 int stabilitycenterlen, /**< length of the stability center */
1197 int nbestdualupdates, /**< number of best Lagrangian values found so far */
1198 int totaliternum /**< total number of iterations of the relax-and-cut algorithm performed so far */
1199 )
1200{
1201 SCIP_Real constant;
1202 SCIP_Real weight;
1203 SCIP_Real alpha;
1204 int i;
1205
1206 constant = MAX(2.0, sepadata->constant);
1207
1208 /* weight factor from the literature on Dantzig-Wolfe decomposition stabilization schemes */
1209 weight = MIN(constant, (totaliternum + 1 + nbestdualupdates) / 2.0);
1210 alpha = 1.0 / weight;
1211
1212 assert(dualvectorlen >= stabilitycenterlen);
1213
1214 /* weighted Lagrangian multipliers */
1215 for( i = 0; i < stabilitycenterlen; i++ )
1216 dualvector[i] = alpha * dualvector[i] + (1 - alpha) * stabilitycenter[i];
1217
1218 for( i = stabilitycenterlen; i < dualvectorlen; i++ )
1219 dualvector[i] = alpha * dualvector[i];
1220}
1221
1222/** stabilize Lagrangian multipliers */
1223static
1224SCIP_RETCODE stabilizeDualVector(
1225 SCIP* scip, /**< SCIP data structure */
1226 SCIP_SEPADATA* sepadata, /**< separator data structure */
1227 SCIP_Real* dualvector, /**< Lagrangian multipliers */
1228 int dualvectorlen, /**< length of the Lagrangian multipliers vector */
1229 SCIP_Real* bestdualvector, /**< best Lagrangian multipliers found so far */
1230 int bestdualvectorlen, /**< length of the best Lagrangian multipliers vector */
1231 int nbestdualupdates, /**< number of best Lagrangian values found so far */
1232 int subgradientiternum, /**< iteration number of the subgradient algorithm */
1233 int totaliternum, /**< total number of iterations of the relax-and-cut algorithm performed so far */
1234 SCIP_Real maxviolscore, /**< weighted average of maximum value of generated cut violations and maximum value of
1235 * complementarity slackness violations, in the current iteration */
1236 SCIP_Real maxviolscoreold, /**< weighted average of maximum value of generated cut violations and maximum value of
1237 * complementarity slackness violations, in the previous iteration */
1238 SCIP_Real nviolscore, /**< weighted average of number of generated cut violations and number of complementarity
1239 * slackness violations, in the current iteration */
1240 SCIP_Real nviolscoreold, /**< weighted average of number of generated cut violations and number of complementarity
1241 * slackness violations, in the previous iteration */
1242 int nlpiters, /**< number of LP iterations taken for solving the Lagrangian dual with fixed multipliers in
1243 * current iteration */
1244 SCIP_Real* ballradius /**< norm ball radius */
1245 )
1246{
1247 if( sepadata->projectiontype > 0 )
1248 {
1249 if( subgradientiternum >= 1 )
1250 {
1251 /* update the ball radius */
1252 updateBallRadius(scip, sepadata, maxviolscore, maxviolscoreold, nviolscore, nviolscoreold, nlpiters,
1253 ballradius);
1254 }
1255
1256 if( sepadata->projectiontype == 1 )
1257 {
1258 /* projection of Lagrangian multipliers onto L1-norm ball */
1259 SCIP_CALL( l1BallProjection(scip, dualvector, dualvectorlen, *ballradius) );
1260 }
1261 else if( sepadata->projectiontype == 2 )
1262 {
1263 /* projection of Lagrangian multipliers onto L2-norm ball */
1264 l2BallProjection(scip, dualvector, dualvectorlen, *ballradius);
1265 }
1266 else if( sepadata->projectiontype == 3 )
1267 {
1268 /* projection of Lagrangian multipliers onto L_inf-norm ball */
1269 linfBallProjection(scip, dualvector, dualvectorlen, *ballradius);
1270 }
1271 }
1272
1273 if( sepadata->stabilitycentertype == 1 )
1274 {
1275 /* weighted Lagrangian multipliers based on best Langrangian multipliers as stability center */
1276 weightedDualVector(sepadata, dualvector, dualvectorlen, bestdualvector, bestdualvectorlen, nbestdualupdates, totaliternum);
1277 }
1278
1279 return SCIP_OKAY;
1280}
1281
1282/** update Lagrangian multipliers */
1283static
1284SCIP_RETCODE updateDualVector(
1285 SCIP* scip, /**< SCIP data structure */
1286 SCIP_SEPADATA* sepadata, /**< separator data structure */
1287 SCIP_Real* dualvector1, /**< Lagrangian multipliers vector to be updated */
1288 SCIP_Real* dualvector2, /**< Lagrangian multipliers vector used for backtracking */
1289 int dualvector2len, /**< length of the Lagrangian multipliers vector used for backtracking */
1290 int ndualvector2updates,/**< number of best Lagrangian values found so far */
1291 int subgradientiternum, /**< iteration number of the subgradient algorithm */
1292 int totaliternum, /**< total number of iterations of the relax-and-cut algorithm performed so far */
1293 SCIP_Real steplength, /**< step length used for updating Lagrangian multipliers */
1294 SCIP_Real* subgradient, /**< subgradient vector */
1295 int ncuts, /**< number of generated cuts so far */
1296 SCIP_Bool backtrack, /**< whether the Lagrangian multipliers need to be backtracked */
1297 SCIP_Real maxviolscore, /**< weighted average of maximum value of generated cut violations and maximum value of
1298 * complementarity slackness violations, in the current iteration */
1299 SCIP_Real maxviolscoreold, /**< weighted average of maximum value of generated cut violations and maximum value of
1300 * complementarity slackness violations, in the previous iteration */
1301 SCIP_Real nviolscore, /**< weighted average of number of generated cut violations and number of complementarity
1302 * slackness violations, in the current iteration */
1303 SCIP_Real nviolscoreold, /**< weighted average of number of generated cut violations and number of complementarity
1304 * slackness violations, in the previous iteration */
1305 int nlpiters, /**< number of LP iterations taken for solving the Lagrangian dual with fixed multipliers in
1306 * current iteration */
1307 SCIP_Bool* dualvecsdiffer, /**< whether the updated Lagrangian multipliers differ from the old one */
1308 SCIP_Real* ballradius /**< norm ball radius */
1309 )
1310{
1311 SCIP_Real* dualvector1copy;
1312 int i;
1313
1314 assert(dualvector2len <= ncuts);
1315 assert(dualvecsdiffer != NULL);
1316
1317 *dualvecsdiffer = FALSE;
1318
1319 /* @todo do allocation and free operations outside only once instead of every time this function is called? */
1320 /* copy of the Lagrangian multipliers to be used to check if the updated vector is different than this */
1321 SCIP_CALL( SCIPallocCleanBufferArray(scip, &dualvector1copy, ncuts) );
1322 for( i = 0; i < ncuts; i++ )
1323 dualvector1copy[i] = dualvector1[i];
1324
1325 /* if backtracking was not identified at the time of the mu parameter update, then update the Lagrangian multipliers
1326 * based on the given subgradient vector
1327 */
1328 if( !backtrack )
1329 {
1330 assert((subgradient != NULL) || (ncuts == 0));
1331 assert(subgradientiternum >= 0);
1332
1333 /* update Lagrangian multipliers */
1334 for( i = 0; i < ncuts; i++ )
1335 {
1336 assert(subgradient != NULL); /* for lint */
1337 dualvector1[i] += steplength * subgradient[i];
1338 }
1339
1340 /* projection onto non-negative orthant */
1341 for( i = 0; i < ncuts; i++ )
1342 {
1343 assert(dualvector1 != NULL); /* for lint */
1344 dualvector1[i] = MAX(dualvector1[i], 0.0);
1345 }
1346
1347 /* stabilization of Lagrangian multipliers */
1348 SCIP_CALL( stabilizeDualVector(scip, sepadata, dualvector1, ncuts, dualvector2, dualvector2len,
1349 ndualvector2updates, subgradientiternum, totaliternum, maxviolscore, maxviolscoreold, nviolscore,
1350 nviolscoreold, nlpiters, ballradius) );
1351
1352 /* projection onto non-negative orthant again in case stabilization changed some components negative*/
1353 for( i = 0; i < ncuts; i++ )
1354 dualvector1[i] = MAX(dualvector1[i], 0.0);
1355 }
1356 /* if backtracking was identified at the time of the mu parameter update, then backtrack the Lagrangian multipliers
1357 * based on the given backtracking multipliers
1358 */
1359 else
1360 {
1361 for( i = 0; i < dualvector2len; i++ )
1362 dualvector1[i] = dualvector2[i];
1363
1364 for( i = dualvector2len; i < ncuts; i++ )
1365 dualvector1[i] = 0.0;
1366 }
1367
1368 /* identify if the vector of Lagrangian multipliers is indeed different after updating */
1369 for( i = 0; i < ncuts; i++ )
1370 {
1371 if( !SCIPisEQ(scip, dualvector1[i], dualvector1copy[i]) )
1372 {
1373 *dualvecsdiffer = TRUE;
1374 break;
1375 }
1376 }
1377
1378 /* free memory */
1379 for( i = 0; i < ncuts; i++ )
1380 dualvector1copy[i] = 0.0;
1381
1382 SCIPfreeCleanBufferArray(scip, &dualvector1copy);
1383
1384 return SCIP_OKAY;
1385}
1386
1387/** check different termination criteria
1388 * @note the criterion based on objvecsdiffer assumes deterministic solving process (i.e., we would get same LP solution
1389 * for "Lagrangian dual with fixed Lagrangian multipliers" when the objective vector remains the same across iterations).
1390 */
1391/* @todo nlpssolved criterion? */
1392static
1393SCIP_RETCODE checkLagrangianDualTermination(
1394 SCIP_SEPADATA* sepadata, /**< separator data structure */
1395 int nnewaddedsoftcuts, /**< number of cuts that were recently penalized and added to the Lagrangian dual's
1396 * objective function */
1397 int nyettoaddsoftcuts, /**< number of cuts that are yet to be penalized and added to the Lagrangian dual's
1398 * objective function */
1399 SCIP_Bool objvecsdiffer, /**< whether the Lagrangian dual's objective function has changed */
1400 int ngeneratedcurrroundcuts, /**< number of cuts generated in the current separation round */
1401 int nmaxgeneratedperroundcuts, /**< maximal number of cuts allowed to generate per separation round */
1402 int ncurrroundlpiters, /**< number of separating LP iterations in the current separation round */
1403 int depth, /**< depth of the current node */
1404 SCIP_Bool* terminate /**< whether to terminate the subgradient algorithm loop */
1405 )
1406{
1407 *terminate = FALSE;
1408
1409 /* check if no new cuts were added to the Lagrangian dual, no cuts are remaining to be added, and the objective
1410 * function of the Lagrangian dual with fixed multipliers had not changed from the previous iteration
1411 */
1412 if( (nnewaddedsoftcuts == 0) && (nyettoaddsoftcuts == 0) && !objvecsdiffer )
1413 *terminate = TRUE;
1414
1415 /* check if allowed number of cuts in this separation round have already been generated */
1416 if( ngeneratedcurrroundcuts >= nmaxgeneratedperroundcuts )
1417 *terminate = TRUE;
1418
1419 /* check if allowed number of cuts in the tree have already been generated */
1420 if( sepadata->ntotalcuts >= sepadata->nmaxtotalcuts )
1421 *terminate = TRUE;
1422
1423 /* check if allowed number of simplex iterations in this separation round have already been used up */
1424 if( (sepadata->nmaxperroundlpiters >= 0) && (ncurrroundlpiters >= sepadata->nmaxperroundlpiters) )
1425 *terminate = TRUE;
1426
1427 /* check if allowed number of simplex iterations in the root node have already been used up */
1428 if( (depth == 0) && (sepadata->nmaxrootlpiters >= 0) && (sepadata->nrootlpiters >= sepadata->nmaxrootlpiters) )
1429 *terminate = TRUE;
1430
1431 /* check if allowed number of simplex iterations in the tree have already been used up */
1432 if( (sepadata->nmaxtotallpiters >= 0) && (sepadata->ntotallpiters >= sepadata->nmaxtotallpiters) )
1433 *terminate = TRUE;
1434
1435 return SCIP_OKAY;
1436}
1437
1438/** solve the LP corresponding to the Lagrangian dual with fixed Lagrangian multipliers */
1439static
1440SCIP_RETCODE solveLagromoryLP(
1441 SCIP* scip, /**< SCIP data structure */
1442 SCIP_SEPADATA* sepadata, /**< separator data structure */
1443 int depth, /**< depth of the current node in the tree */
1444 SCIP_Real origobjoffset, /**< objective offset in the current node's relaxation */
1445 SCIP_Bool* solfound, /**< whether an LP optimal solution has been found */
1446 SCIP_SOL* sol, /**< data structure to store LP optimal solution, if found */
1447 SCIP_Real* solvals, /**< values of the LP optimal solution, if found */
1448 SCIP_Real* objval, /**< optimal objective value of the LP optimal solution, if found */
1449 int* ncurrroundlpiters /**< number of LP iterations taken for solving Lagrangian dual problems with fixed multipliers
1450 * in the current separator round */
1451 )
1452{
1453 SCIP_Real timelimit;
1454 SCIP_COL** cols;
1455 SCIP_COL* col;
1456 SCIP_VAR* var;
1457 SCIP_LPI* lpi;
1458 SCIP_Bool lperror;
1459 SCIP_Bool cutoff;
1460 SCIP_LPSOLSTAT stat;
1461 SCIP_Longint ntotallpiters;
1462 SCIP_Longint nlpiters;
1463 int ncols;
1464 int iterlimit;
1465
1466 assert(solfound != NULL);
1467 assert(sol != NULL);
1468 assert(solvals != NULL);
1469 assert(ncurrroundlpiters != NULL);
1470 assert(objval != NULL);
1471
1472 *solfound = FALSE;
1473 lperror = FALSE;
1474 cutoff = FALSE;
1475 iterlimit = -1;
1476 lpi = sepadata->lpiwithsoftcuts;
1477
1478 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
1479
1480 /* set time limit */
1481 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1482 if( !SCIPisInfinity(scip, timelimit) )
1483 {
1484 timelimit -= SCIPgetSolvingTime(scip);
1485 if( timelimit <= 0.0 )
1486 {
1487 SCIPdebugMsg(scip, "skip Lagromory cut generation since no time left\n");
1488 goto TERMINATE;
1489 }
1490
1491 /* @note the following direct LPI call is being used because of the lack of an equivalent function call in
1492 * scip_lp.c (lpSetRealpar exists in lp.c though)
1493 */
1494 SCIP_CALL( SCIPlpiSetRealpar(lpi, SCIP_LPPAR_LPTILIM, timelimit) );
1495 }
1496
1497 /* find iteration limit */
1498 if( (depth == 0) &&
1499 (sepadata->perrootlpiterfactor >= 0.0 && !SCIPisInfinity(scip, sepadata->perrootlpiterfactor)) )
1500 {
1501 iterlimit = (int)(sepadata->perrootlpiterfactor * SCIPgetNRootFirstLPIterations(scip));
1502 }
1503 else if( (depth > 0) &&
1504 (sepadata->perlpiterfactor >= 0.0 && !SCIPisInfinity(scip, sepadata->perlpiterfactor)) )
1505 {
1506 iterlimit = (int)(sepadata->perlpiterfactor * SCIPgetNNodeInitLPIterations(scip));
1507 }
1508 if( sepadata->nmaxperroundlpiters >= 0 )
1509 {
1510 if( sepadata->nmaxperroundlpiters - *ncurrroundlpiters >= 0 )
1511 {
1512 if( iterlimit >= 0 )
1513 iterlimit = MIN(iterlimit, sepadata->nmaxperroundlpiters - *ncurrroundlpiters);
1514 else
1515 iterlimit = sepadata->nmaxperroundlpiters - *ncurrroundlpiters;
1516 }
1517 else
1518 iterlimit = 0;
1519 }
1520 /* @todo impose a finite iteration limit only when the dualvector changes from zero to non-zero for the first time because
1521 * many simplex pivots are performed in this case even with warm starting (compared to the case when the
1522 * dualvector changes from non-zero to non-zero)
1523 */
1524
1525 /* solve the LP with an iteration limit and get number of simplex iterations taken */
1526 ntotallpiters = SCIPgetNLPIterations(scip);
1527
1528 SCIP_CALL( SCIPsolveDiveLP(scip, iterlimit, &lperror, &cutoff) );
1529
1530 nlpiters = SCIPgetNLPIterations(scip) - ntotallpiters;
1531
1532 /* get the solution and objective value if optimal */
1533 stat = SCIPgetLPSolstat(scip);
1534
1535 /* @todo is there any way to accept terminations due to iterlimit and timelimit as well? It is not possible
1536 * currently because primal sol is not saved in these cases.
1537 */
1538 /* @note ideally, only primal feasibility is sufficient. But, there is no such option with SCIPgetLPSolstat. */
1539 if( stat == SCIP_LPSOLSTAT_OPTIMAL )
1540 {
1541 if( SCIPisLPSolBasic(scip) )
1542 {
1543 int i;
1544
1545 *solfound = TRUE;
1546
1547 /* update sol */
1548 for( i = 0; i < ncols; ++i )
1549 {
1550 col = cols[i];
1551 assert(col != NULL);
1552
1553 var = SCIPcolGetVar(col);
1554
1555 solvals[i] = SCIPcolGetPrimsol(col);
1556 SCIP_CALL( SCIPsetSolVal(scip, sol, var, solvals[i]) );
1557 }
1558
1559 *objval = SCIPgetLPObjval(scip);
1560 *objval = *objval + origobjoffset;
1561 }
1562 }
1563
1564 /* update some statistics */
1565 if( depth == 0 )
1566 sepadata->nrootlpiters += (int)nlpiters;
1567
1568 sepadata->ntotallpiters += (int)nlpiters;
1569 *ncurrroundlpiters += (int)nlpiters;
1570
1571TERMINATE:
1572 return SCIP_OKAY;
1573}
1574
1575/** solve the LP corresponding to the node relaxation upon adding all the generated cuts */
1576static
1577SCIP_RETCODE solveLPWithHardCuts(
1578 SCIP* scip, /**< SCIP data structure */
1579 SCIP_SEPADATA* sepadata, /**< separator data structure */
1580 SCIP_Bool* solfound, /**< whether an LP optimal solution has been found */
1581 SCIP_SOL* sol, /**< data structure to store LP optimal solution, if found */
1582 SCIP_Real* solvals /**< values of the LP optimal solution, if found */
1583 )
1584{
1585 SCIP_Real timelimit;
1586 SCIP_COL** cols;
1587 SCIP_COL* col;
1588 SCIP_VAR* var;
1589 int ncols;
1590
1591 assert(solfound != NULL);
1592 assert(sol != NULL);
1593 assert(solvals != NULL);
1594
1595 *solfound = FALSE;
1596
1597 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
1598
1599 /* set time limit */
1600 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1601 if( !SCIPisInfinity(scip, timelimit) )
1602 {
1603 timelimit -= SCIPgetSolvingTime(scip);
1604 if( timelimit <= 0.0 )
1605 {
1606 SCIPdebugMsg(scip, "skip Lagromory cut generation since no time left\n");
1607 goto TERMINATE;
1608 }
1609 SCIP_CALL( SCIPlpiSetRealpar(sepadata->lpiwithhardcuts, SCIP_LPPAR_LPTILIM, timelimit) );
1610 }
1611
1612 /* solve the LP */
1613 SCIP_CALL( SCIPlpiSolvePrimal(sepadata->lpiwithhardcuts) );
1614
1615 /* get the solution if primal feasible */
1616 if( SCIPlpiIsPrimalFeasible(sepadata->lpiwithhardcuts) )
1617 {
1618 int i;
1619
1620 *solfound = TRUE;
1621 SCIP_CALL( SCIPlpiGetSol(sepadata->lpiwithhardcuts, NULL, solvals, NULL, NULL, NULL) );
1622
1623 /* update sol */
1624 for( i = 0; i < ncols; ++i )
1625 {
1626 col = cols[i];
1627 assert(col != NULL);
1628
1629 var = SCIPcolGetVar(col);
1630
1631 SCIP_CALL( SCIPsetSolVal(scip, sol, var, solvals[i]) );
1632 }
1633 }
1634
1635TERMINATE:
1636 return SCIP_OKAY;
1637}
1638
1639/** construct a cut based on the input cut coefficients, sides, etc */
1640static
1641SCIP_RETCODE constructCutRow(
1642 SCIP* scip, /**< SCIP data structure */
1643 SCIP_SEPA* sepa, /**< pointer to the separator */
1644 SCIP_SEPADATA* sepadata, /**< separator data structure */
1645 int mainiternum, /**< iteration number of the outer loop of the relax-and-cut algorithm */
1646 int subgradientiternum, /**< iteration number of the subgradient algorithm */
1647 int cutnnz, /**< number of nonzeros in cut */
1648 int* cutinds, /**< column indices in cut */
1649 SCIP_Real* cutcoefs, /**< cut cofficients */
1650 SCIP_Real cutefficacy, /**< cut efficacy */
1651 SCIP_Real cutrhs, /**< RHS of cut */
1652 SCIP_Bool cutislocal, /**< whether cut is local */
1653 int cutrank, /**< rank of cut */
1654 SCIP_ROW** generatedcuts, /**< array of generated cuts */
1655 SCIP_Real* generatedcutefficacies, /**< array of generated cut efficacies w.r.t. the respective LP bases used for cut
1656 * generations */
1657 int ngeneratedcurrroundcuts, /**< number of cuts generated until the previous basis in the current separation round */
1658 int* ngeneratednewcuts, /**< number of new cuts generated using the current basis */
1659 SCIP_Bool* cutoff /**< should the current node be cutoff? */
1660 )
1661{
1662 SCIP_COL** cols;
1663 SCIP_Real minactivity;
1664 SCIP_Real maxactivity;
1665 SCIP_Real lhs;
1666 SCIP_Real rhs;
1667
1668 assert(scip != NULL);
1669 assert(mainiternum >= 0);
1670 assert(ngeneratednewcuts != NULL);
1671 assert(cutoff != NULL);
1672
1673 *cutoff = FALSE;
1674
1675 if( cutnnz == 0 && SCIPisFeasNegative(scip, cutrhs) ) /*lint !e644*/
1676 {
1677 SCIPdebugMsg(scip, " -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", cutrhs);
1678 *cutoff = TRUE;
1679 return SCIP_OKAY;
1680 }
1681
1682 /* only take efficient cuts */
1683 if( SCIPisEfficacious(scip, cutefficacy) )
1684 {
1685 SCIP_ROW* cut;
1686 SCIP_VAR* var;
1687 char cutname[SCIP_MAXSTRLEN];
1688 int v;
1689
1690 /* construct cut name */
1691 if( subgradientiternum >= 0 )
1692 {
1693 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s_%" SCIP_LONGINT_FORMAT "_%d" "_%d" "_%d", SCIPsepaGetName(sepa),
1694 sepadata->ncalls, mainiternum, subgradientiternum, ngeneratedcurrroundcuts + *ngeneratednewcuts);
1695 }
1696 else
1697 {
1698 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s_%" SCIP_LONGINT_FORMAT "_%d" "_%d", SCIPsepaGetName(sepa),
1699 sepadata->ncalls, mainiternum, ngeneratedcurrroundcuts + *ngeneratednewcuts);
1700 }
1701
1702 /* create empty cut */
1703 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE,
1704 sepadata->dynamiccuts) );
1705
1706 /* set cut rank */
1707 SCIProwChgRank(cut, cutrank); /*lint !e644*/
1708
1709 /* cache the row extension and only flush them if the cut gets added */
1710 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
1711
1712 cols = SCIPgetLPCols(scip);
1713
1714 /* collect all non-zero coefficients */
1715 for( v = 0; v < cutnnz; ++v )
1716 {
1717 var = SCIPcolGetVar(cols[cutinds[v]]);
1718 SCIP_CALL( SCIPaddVarToRow(scip, cut, var, cutcoefs[v]) );
1719 }
1720
1721 /* flush all changes before adding the cut */
1722 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
1723
1724 if( SCIProwGetNNonz(cut) == 0 )
1725 {
1726 assert( SCIPisFeasNegative(scip, cutrhs) );
1727 SCIPdebugMsg(scip, " -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", cutrhs);
1728 *cutoff = TRUE;
1729 return SCIP_OKAY;
1730 }
1731 else
1732 {
1733 /* gathering lhs and rhs again in case the separator is extended later to add other cuts/constraints that may
1734 * have non-inf lhs or inf rhs */
1735 lhs = SCIProwGetLhs(cut);
1736 rhs = SCIProwGetRhs(cut);
1737 assert(SCIPisInfinity(scip, -lhs));
1738 assert(!SCIPisInfinity(scip, rhs));
1739
1740 SCIPdebugMsg(scip, " -> %s cut <%s>: rhs=%f, eff=%f\n", "lagromory", cutname, cutrhs, cutefficacy);
1741
1742 /* check if the cut leads to infeasibility (i.e., *cutoff = TRUE) */
1743 {
1744 /* modifiable cuts cannot be declared infeasible, since we don't know all coefficients */
1745 if( SCIProwIsModifiable(cut) )
1746 *cutoff = FALSE;
1747
1748 /* check for activity infeasibility */
1749 minactivity = SCIPgetRowMinActivity(scip, cut);
1750 maxactivity = SCIPgetRowMaxActivity(scip, cut);
1751
1752 if( (!SCIPisInfinity(scip, rhs) && SCIPisFeasPositive(scip, minactivity - rhs)) ||
1753 (!SCIPisInfinity(scip, -lhs) && SCIPisFeasNegative(scip, maxactivity - lhs)) )
1754 {
1755 SCIPdebugMsg(scip, "cut <%s> is infeasible (sides=[%g,%g], act=[%g,%g])\n",
1756 SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
1757 *cutoff = TRUE;
1758 }
1759 }
1760
1761 /* store the newly generated cut in an array and update some statistics */
1762 generatedcuts[ngeneratedcurrroundcuts + *ngeneratednewcuts] = cut;
1763 generatedcutefficacies[ngeneratedcurrroundcuts + *ngeneratednewcuts] = cutefficacy;
1764 ++(*ngeneratednewcuts);
1765 }
1766 }
1767
1768 return SCIP_OKAY;
1769}
1770
1771/** aggregated generated cuts based on the best Lagrangian multipliers */
1772static
1773SCIP_RETCODE aggregateGeneratedCuts(
1774 SCIP* scip, /**< SCIP data structure */
1775 SCIP_SEPA* sepa, /**< pointer to the separator */
1776 SCIP_SEPADATA* sepadata, /**< separator data structure */
1777 SCIP_ROW** generatedcuts, /**< cuts generated in the current separation round */
1778 SCIP_Real* bestdualvector, /**< best Lagrangian multipliers vector */
1779 int bestdualvectorlen, /**< length of the best Lagrangian multipliers vector */
1780 SCIP_ROW** aggrcuts, /**< aggregated cuts generated so far in the current separation round */
1781 int* naggrcuts, /**< number of aggregated cuts generated so far in the current separation round */
1782 SCIP_Bool* cutoff /**< should the current node be cutoff? */
1783 )
1784{
1785 SCIP_Real* cutvals; /* cut cofficients */
1786 SCIP_COL** cutcols;
1787 SCIP_COL** cols;
1788 SCIP_VAR* var;
1789 SCIP_ROW* cut;
1790 SCIP_ROW* aggrcut;
1791 SCIP_Real minactivity;
1792 SCIP_Real maxactivity;
1793 SCIP_Real cutlhs;
1794 SCIP_Real cutrhs;
1795 SCIP_Real cutconst;
1796 SCIP_Real aggrcutlhs;
1797 SCIP_Real aggrcutrhs;
1798 SCIP_Real aggrcutconst;
1799 SCIP_Real* aggrcutvals;
1800 SCIP_Real* aggrcutcoefs;
1801 SCIP_Real multiplier;
1802 SCIP_Bool aggrcutislocal;
1803 SCIP_Bool aggrindicator;
1804 SCIP_Real* tmpcutvals;
1805 SCIP_Real QUAD(quadterm);
1806 SCIP_Real QUAD(tmpcutconst);
1807 SCIP_Real QUAD(tmpcutrhs);
1808 SCIP_Real QUAD(quadprod);
1809 char aggrcutname[SCIP_MAXSTRLEN];
1810 int cutnnz; /* number of nonzeros in cut */
1811 int aggrcutnnz;
1812 int* aggrcutinds; /* column indices in cut */
1813 int aggrcutrank; /* rank of cut */
1814 int cutrank;
1815 int ncols;
1816 int collppos;
1817 int nlocalcuts;
1818 int i;
1819 int j;
1820
1821 assert(scip != NULL);
1822 assert(naggrcuts != NULL);
1823 assert(cutoff != NULL);
1824
1825 *cutoff = FALSE;
1826 aggrcutlhs = -SCIPinfinity(scip);
1827 aggrcutnnz = 0;
1828 aggrcutrank = -1;
1829 nlocalcuts = 0;
1830 aggrindicator = FALSE;
1831
1832 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
1833
1834 /* allocate memory */
1835 SCIP_CALL( SCIPallocCleanBufferArray(scip, &tmpcutvals, QUAD_ARRAY_SIZE(ncols)) );
1836 QUAD_ASSIGN(tmpcutconst, 0.0);
1837 QUAD_ASSIGN(tmpcutrhs, 0.0);
1838 SCIP_CALL( SCIPallocCleanBufferArray(scip, &aggrcutvals, ncols) );
1839 SCIP_CALL( SCIPallocBufferArray(scip, &aggrcutcoefs, ncols) );
1840 SCIP_CALL( SCIPallocBufferArray(scip, &aggrcutinds, ncols) );
1841
1842 /* aggregate cuts based on the input Lagrangian multipliers */
1843 for( i = 0; i < bestdualvectorlen; i++ )
1844 {
1845 multiplier = bestdualvector[i];
1846 if( SCIPisGE(scip, multiplier, 1e-4) )
1847 {
1848 cut = generatedcuts[i];
1849 cutnnz = SCIProwGetNNonz(cut);
1850 cutlhs = SCIProwGetLhs(cut);
1851 cutrhs = SCIProwGetRhs(cut);
1852 assert(SCIPisInfinity(scip, -cutlhs));
1853 assert(!SCIPisInfinity(scip, cutrhs));
1854 cutvals = SCIProwGetVals(cut);
1855 cutcols = SCIProwGetCols(cut);
1856 cutconst = SCIProwGetConstant(cut);
1857
1858 for( j = 0; j < cutnnz; j++ )
1859 {
1860 collppos = SCIPcolGetLPPos(cutcols[j]);
1861 assert(collppos >= 0);
1862 assert(collppos <= ncols);
1863
1864 QUAD_ARRAY_LOAD(quadterm, tmpcutvals, collppos);
1865 SCIPquadprecProdDD(quadprod, multiplier, cutvals[j]);
1866 SCIPquadprecSumQQ(quadterm, quadterm, quadprod);
1867 QUAD_ARRAY_STORE(tmpcutvals, collppos, quadterm);
1868 }
1869
1870 SCIPquadprecProdDD(quadprod, multiplier, cutconst);
1871 SCIPquadprecSumQQ(tmpcutconst, tmpcutconst, quadprod);
1872 SCIPquadprecProdDD(quadprod, multiplier, cutrhs);
1873 SCIPquadprecSumQQ(tmpcutrhs, tmpcutrhs, quadprod);
1874
1875 cutrank = SCIProwGetRank(cut);
1876 aggrcutrank = MAX(aggrcutrank, cutrank);
1877 nlocalcuts += (SCIProwIsLocal(cut) ? 1 : 0);
1878 aggrindicator = TRUE;
1879 }
1880 }
1881 /* if at least one cut is local, then the aggregated cut is local */
1882 aggrcutislocal = (nlocalcuts > 0 ? TRUE : FALSE);
1883
1884 /* if the aggregation was successful, then create an empty row and build a cut */
1885 if( aggrindicator )
1886 {
1887 aggrcutconst = QUAD_TO_DBL(tmpcutconst);
1888 aggrcutrhs = QUAD_TO_DBL(tmpcutrhs);
1889
1890 /* build sparse representation of the aggregated cut */
1891 for( i = 0; i < ncols; i++ )
1892 {
1893 QUAD_ARRAY_LOAD(quadterm, tmpcutvals, i);
1894 aggrcutvals[i] = QUAD_TO_DBL(quadterm);
1895 if( !SCIPisZero(scip, aggrcutvals[i]) )
1896 {
1897 aggrcutcoefs[aggrcutnnz] = aggrcutvals[i];
1898 aggrcutinds[aggrcutnnz] = i;
1899 aggrcutnnz++;
1900 }
1901 }
1902
1903 if( aggrcutnnz == 0 && SCIPisFeasNegative(scip, aggrcutrhs) ) /*lint !e644*/
1904 {
1905 SCIPdebugMsg(scip, " -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", aggrcutrhs);
1906 *cutoff = TRUE;
1907 goto TERMINATE;
1908 }
1909
1910 /* construct aggregated cut name */
1911 (void) SCIPsnprintf(aggrcutname, SCIP_MAXSTRLEN, "%s_%" SCIP_LONGINT_FORMAT "_aggregated", SCIPsepaGetName(sepa),
1912 sepadata->ncalls);
1913
1914 /* create empty cut */
1915 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &aggrcut, sepa, aggrcutname, aggrcutlhs - aggrcutconst, aggrcutrhs -
1916 aggrcutconst, aggrcutislocal, FALSE, sepadata->dynamiccuts) );
1917
1918 /* set cut rank */
1919 SCIProwChgRank(aggrcut, aggrcutrank); /*lint !e644*/
1920
1921 /* cache the row extension and only flush them if the cut gets added */
1922 SCIP_CALL( SCIPcacheRowExtensions(scip, aggrcut) );
1923
1924 /* collect all non-zero coefficients */
1925 for( i = 0; i < aggrcutnnz; i++ )
1926 {
1927 var = SCIPcolGetVar(cols[aggrcutinds[i]]);
1928 SCIP_CALL( SCIPaddVarToRow(scip, aggrcut, var, aggrcutcoefs[i]) );
1929 }
1930
1931 /* flush all changes before adding the cut */
1932 SCIP_CALL( SCIPflushRowExtensions(scip, aggrcut) );
1933
1934 if( SCIProwGetNNonz(aggrcut) == 0 )
1935 {
1936 assert( SCIPisFeasNegative(scip, aggrcutrhs) );
1937 SCIPdebugMsg(scip, " -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", aggrcutrhs);
1938 *cutoff = TRUE;
1939 goto TERMINATE;
1940 }
1941 else
1942 {
1943 /* gathering lhs and rhs again in case the separator is extended later to add other cuts/constraints that may
1944 * have non-inf lhs or inf rhs */
1945 cutlhs = SCIProwGetLhs(aggrcut);
1946 cutrhs = SCIProwGetRhs(aggrcut);
1947 assert(SCIPisInfinity(scip, -cutlhs));
1948 assert(!SCIPisInfinity(scip, cutrhs));
1949
1950 SCIPdebugMsg(scip, " -> %s cut <%s>: rhs=%f\n", "lagromory", aggrcutname, aggrcutrhs);
1951
1952 /* check if the cut leads to infeasibility (i.e., *cutoff = TRUE) */
1953 {
1954 /* modifiable cuts cannot be declared infeasible, since we don't know all coefficients */
1955 if( SCIProwIsModifiable(aggrcut) )
1956 *cutoff = FALSE;
1957
1958 /* check for activity infeasibility */
1959 minactivity = SCIPgetRowMinActivity(scip, aggrcut);
1960 maxactivity = SCIPgetRowMaxActivity(scip, aggrcut);
1961
1962 if( (!SCIPisInfinity(scip, cutrhs) && SCIPisFeasPositive(scip, minactivity - cutrhs)) ||
1963 (!SCIPisInfinity(scip, -cutlhs) && SCIPisFeasNegative(scip, maxactivity - cutlhs)) )
1964 {
1965 SCIPdebugMsg(scip, "cut <%s> is infeasible (sides=[%g,%g], act=[%g,%g])\n",
1966 SCIProwGetName(aggrcut), cutlhs, cutrhs, minactivity, maxactivity);
1967 *cutoff = TRUE;
1968 }
1969 }
1970
1971 /* add the aggregated cut to a separate data structure */
1972 aggrcuts[*naggrcuts] = aggrcut;
1973 (*naggrcuts)++;
1974 }
1975
1976 QUAD_ASSIGN(quadterm, 0.0);
1977 for( i = 0; i < ncols; i++ )
1978 {
1979 aggrcutvals[i] = 0.0;
1980 QUAD_ARRAY_STORE(tmpcutvals, i, quadterm);
1981 }
1982 }
1983
1984TERMINATE:
1985 /* free memory */
1986 SCIPfreeBufferArray(scip, &aggrcutinds);
1987 SCIPfreeBufferArray(scip, &aggrcutcoefs);
1988 SCIPfreeCleanBufferArray(scip, &aggrcutvals);
1989 SCIPfreeCleanBufferArray(scip, &tmpcutvals);
1990
1991 return SCIP_OKAY;
1992}
1993
1994/** main method: LP solution separation method of separator */
1995static
1996SCIP_RETCODE generateGMICuts(
1997 SCIP* scip, /**< SCIP data structure */
1998 SCIP_SEPA* sepa, /**< pointer to the separator */
1999 SCIP_SEPADATA* sepadata, /**< separator data structure */
2000 int mainiternum, /**< iteration number of the outer loop of the relax-and-cut algorithm */
2001 int subgradientiternum, /**< iteration number of the subgradient algorithm */
2002 SCIP_SOL* sol, /**< LP solution to be used for cut generation */
2003 SCIP_Real* solvals, /**< values of the LP solution to be used for cut generation */
2004 int nmaxgeneratedperroundcuts, /**< maximal number of cuts allowed to generate per separation round */
2005 SCIP_Bool allowlocal, /**< should locally valid cuts be generated? */
2006 SCIP_ROW** generatedcurrroundcuts, /**< cuts generated in the current separation round */
2007 SCIP_Real* generatedcutefficacies, /**< array of generated cut efficacies w.r.t. the respective LP bases used for cut
2008 * generations */
2009 int ngeneratedcurrroundcuts, /**< number of cuts generated until the previous basis in the current separation round */
2010 int* ngeneratednewcuts, /**< number of new cuts generated using the current basis */
2011 int depth, /**< depth of the current node in the tree */
2012 SCIP_Bool* cutoff /**< should the current node be cutoff? */
2013 )
2014{
2015 SCIP_Real minfrac;
2016 SCIP_Real maxfrac;
2017 SCIP_Real frac;
2018 SCIP_Real* basisfrac;
2019 SCIP_Real* binvrow;
2020 SCIP_AGGRROW* aggrrow;
2021 SCIP_Bool success;
2022 SCIP_Real* cutcoefs;
2023 SCIP_Real cutrhs;
2024 SCIP_Real cutefficacy;
2025 SCIP_Bool cutislocal;
2026 SCIP_ROW** rows;
2027 SCIP_COL** cols;
2028 SCIP_VAR* var;
2029 SCIP_ROW* row;
2030 int cutrank;
2031 int cutnnz;
2032 int* cutinds;
2033 int* basisind;
2034 int* inds;
2035 int nrows;
2036 int ncols;
2037 int* basisperm;
2038 int k;
2039 int c;
2040 int ninds;
2041 int nmaxcutsperlp;
2042 int i;
2043
2044 assert(ngeneratednewcuts != NULL);
2045
2046 minfrac = sepadata->away;
2047 maxfrac = 1.0 - sepadata->away;
2048 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
2049 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
2050 *ngeneratednewcuts = 0;
2051 nmaxcutsperlp = ((depth == 0) ? sepadata->nmaxcutsperlproot : sepadata->nmaxcutsperlp);
2052
2053 /* allocate memory */
2054 SCIP_CALL( SCIPallocBufferArray(scip, &basisperm, nrows) );
2055 SCIP_CALL( SCIPallocBufferArray(scip, &basisfrac, nrows) );
2056 SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
2057 SCIP_CALL( SCIPallocBufferArray(scip, &inds, nrows) );
2058 SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
2059 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
2060 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, ncols) );
2061 SCIP_CALL( SCIPaggrRowCreate(scip, &aggrrow) );
2062
2063 SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
2064
2065 /* check if the rows of the simplex tableau are suitable for cut generation and build an array of fractions */
2066 for( i = 0; i < nrows; ++i )
2067 {
2068 frac = 0.0;
2069
2070 c = basisind[i];
2071
2072 basisperm[i] = i;
2073
2074 /* if the simplex tableau row corresponds to an LP column */
2075 if( c >= 0 )
2076 {
2077 assert(c < ncols);
2078
2079 var = SCIPcolGetVar(cols[c]);
2080 /* if the column is non-continuous one */
2081 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
2082 {
2083 frac = SCIPfeasFrac(scip, solvals[c]);
2084 frac = MIN(frac, 1.0 - frac);
2085 }
2086 }
2087 /* if the simplex tableau row corresponds to an LP row and separation on rows is allowed */
2088 else if( sepadata->separaterows )
2089 {
2090 assert(0 <= -c-1);
2091 assert(-c-1 < nrows);
2092
2093 row = rows[-c-1];
2094 /* if the row is suitable for cut generation */
2095 if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
2096 {
2097 frac = SCIPfeasFrac(scip, SCIPgetRowActivity(scip, row));
2098 frac = MIN(frac, 1.0 - frac);
2099 }
2100 }
2101
2102 if( frac >= minfrac )
2103 {
2104 /* slightly change fractionality to have random order for equal fractions */
2105 basisfrac[i] = frac + SCIPrandomGetReal(sepadata->randnumgen, -1e-6, 1e-6);
2106 }
2107 else
2108 {
2109 basisfrac[i] = 0.0;
2110 }
2111 }
2112
2113 /* if there is a need to sort the fractionalities */
2114 if( sepadata->sortcutoffsol )
2115 {
2116 /* sort basis indices by fractionality */
2117 SCIPsortDownRealInt(basisfrac, basisperm, nrows);
2118 }
2119
2120 /* for all basic columns belonging to integer variables, try to generate a GMI cut */
2121 for( i = 0; i < nrows && !SCIPisStopped(scip) && !*cutoff; ++i )
2122 {
2123 if( (ngeneratedcurrroundcuts + *ngeneratednewcuts >= nmaxgeneratedperroundcuts) ||
2124 (sepadata->ntotalcuts + *ngeneratednewcuts >= sepadata->nmaxtotalcuts) ||
2125 (*ngeneratednewcuts >= nmaxcutsperlp) )
2126 break;
2127
2128 ninds = -1;
2129 cutefficacy = 0.0;
2130
2131 /* either break the loop or proceed to the next iteration if the fractionality is zero */
2132 if( basisfrac[i] == 0.0 )
2133 {
2134 if( sepadata->sortcutoffsol )
2135 break;
2136 else
2137 continue;
2138 }
2139
2140 k = basisperm[i];
2141
2142 /* get the row of B^-1 for this basic integer variable with fractional solution value and call aggregate function */
2143 SCIP_CALL( SCIPgetLPBInvRow(scip, k, binvrow, inds, &ninds) );
2144
2145 SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, binvrow, inds, ninds, sepadata->sidetypebasis, allowlocal, 2,
2146 (int) MAXAGGRLEN(ncols), &success) );
2147
2148 if( !success )
2149 continue;
2150
2151 /* @todo Currently we are using the SCIPcalcMIR() function to compute the coefficients of the Gomory
2152 * cut. Alternatively, we could use the direct version (see thesis of Achterberg formula (8.4)) which
2153 * leads to cut a of the form \sum a_i x_i \geq 1. Rumor has it that these cuts are better.
2154 */
2155
2156 /* try to create GMI cut out of the aggregation row */
2157 SCIP_CALL( SCIPcalcMIR(scip, sol, POSTPROCESS, BOUNDSWITCH, USEVBDS, allowlocal, FIXINTEGRALRHS, NULL,
2158 NULL, minfrac, maxfrac, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank,
2159 &cutislocal, &success) );
2160
2161 if( success )
2162 {
2163 assert(allowlocal || !cutislocal); /*lint !e644*/
2164
2165 SCIP_CALL( constructCutRow(scip, sepa, sepadata, mainiternum, subgradientiternum, cutnnz, cutinds, cutcoefs,
2166 cutefficacy, cutrhs, cutislocal, cutrank, generatedcurrroundcuts, generatedcutefficacies,
2167 ngeneratedcurrroundcuts, ngeneratednewcuts, cutoff));
2168 }
2169 }
2170
2171 /* free temporary memory */
2172 SCIPfreeBufferArray(scip, &cutinds);
2173 SCIPfreeBufferArray(scip, &cutcoefs);
2174 SCIPfreeBufferArray(scip, &basisind);
2175 SCIPfreeBufferArray(scip, &inds);
2176 SCIPfreeBufferArray(scip, &binvrow);
2177 SCIPfreeBufferArray(scip, &basisfrac);
2178 SCIPfreeBufferArray(scip, &basisperm);
2179 SCIPaggrRowFree(scip, &aggrrow);
2180
2181 return SCIP_OKAY;
2182}
2183
2184/** update objective vector w.r.t. the fixed Lagrangian multipliers */
2185static
2186SCIP_RETCODE updateObjectiveVector(
2187 SCIP* scip, /**< SCIP data structure */
2188 SCIP_Real* dualvector, /**< Lagrangian multipliers vector */
2189 SCIP_ROW** cuts, /**< cuts generated so far in the current separation round */
2190 int ncuts, /**< number of cuts generated so far in the current separation round */
2191 SCIP_Real* origobjcoefs, /**< original objective function coefficients of the node linear relaxation */
2192 SCIP_Bool* objvecsdiffer /**< whether the updated objective function coefficients differ from the old ones */
2193 )
2194{
2195 SCIP_Real* objvals;
2196 SCIP_Real* prod;
2197 SCIP_Real* oldobjvals;
2198 SCIP_Real* cutvals;
2199 SCIP_COL** cutcols;
2200 SCIP_COL** cols;
2201 SCIP_VAR* var;
2202 int cutnnz;
2203 int collppos;
2204 int ncols;
2205 int i;
2206 int j;
2207
2208 assert(objvecsdiffer != NULL);
2209 assert(ncuts > 0);
2210
2211 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
2212
2213 /* allocate memory */
2214 SCIP_CALL( SCIPallocBufferArray(scip, &objvals, ncols) );
2215 SCIP_CALL( SCIPallocBufferArray(scip, &oldobjvals, ncols) );
2216 SCIP_CALL( SCIPallocCleanBufferArray(scip, &prod, ncols) );
2217 *objvecsdiffer = FALSE;
2218
2219 /* find the product of Lagrangian multipliers and cut coefficients */
2220 for( i = 0; i < ncuts; i++ )
2221 {
2222 if( !SCIPisZero(scip, dualvector[i]) )
2223 {
2224 assert(!(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])) && SCIPisInfinity(scip, SCIProwGetRhs(cuts[i]))));
2225 assert(SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])));
2226 assert(!SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])));
2227
2228 cutnnz = SCIProwGetNNonz(cuts[i]);
2229 assert(cutnnz <= ncols);
2230 cutvals = SCIProwGetVals(cuts[i]);
2231 cutcols = SCIProwGetCols(cuts[i]);
2232
2233 for( j = 0; j < cutnnz; ++j )
2234 {
2235 collppos = SCIPcolGetLPPos(cutcols[j]);
2236 assert(collppos >= 0);
2237 assert(collppos <= ncols);
2238
2239 prod[collppos] += dualvector[i] * cutvals[j];
2240 }
2241 }
2242 }
2243
2244 /* change objective coefficients */
2245 for( i = 0; i < ncols; i++ )
2246 {
2247 var = SCIPcolGetVar(cols[i]);
2248 oldobjvals[i] = SCIPgetVarObjDive(scip, var);
2249 objvals[i] = origobjcoefs[i] + prod[i];
2250
2251 SCIP_CALL( SCIPchgVarObjDive(scip, var, objvals[i]) );
2252
2253 /* identify if the updated objective vector is indeed different from the previous one */
2254 if( !(*objvecsdiffer) && !SCIPisEQ(scip, oldobjvals[i], objvals[i]) )
2255 *objvecsdiffer = TRUE;
2256 }
2257
2258 for( i = 0; i < ncols; i++)
2259 prod[i] = 0.0;
2260
2261 /* free memory */
2262 SCIPfreeCleanBufferArray(scip, &prod);
2263 SCIPfreeBufferArray(scip, &oldobjvals);
2264 SCIPfreeBufferArray(scip, &objvals);
2265
2266 return SCIP_OKAY;
2267}
2268
2269/** add GMI cuts to the objective function of the Lagrangian dual problem by introducing new Lagrangian multipliers */
2270static
2271SCIP_RETCODE addGMICutsAsSoftConss(
2272 SCIP_Real* dualvector, /**< Lagrangian multipliers vector */
2273 int ngeneratedcuts, /**< number of cuts generated so far in the current separation round */
2274 int* naddedcuts, /**< number of cuts added so far in the current separation round to the Lagrangian dual problem
2275 * upon penalization */
2276 int* nnewaddedsoftcuts /**< number of cuts added newly to the Lagrangian dual problem upon penalization */
2277 )
2278{
2279 int i;
2280
2281 assert(*naddedcuts <= ngeneratedcuts);
2282
2283 /* set the initial penalty of the newly penalized cuts as zero */
2284 for( i = *naddedcuts; i < ngeneratedcuts; i++ )
2285 dualvector[i] = 0.0;
2286
2287 *nnewaddedsoftcuts = ngeneratedcuts - *naddedcuts;
2288 *naddedcuts = ngeneratedcuts;
2289
2290 return SCIP_OKAY;
2291}
2292
2293/** solve the Lagrangian dual problem */
2294static
2295SCIP_RETCODE solveLagrangianDual(
2296 SCIP* scip, /**< SCIP data structure */
2297 SCIP_SEPA* sepa, /**< pointer to the separator */
2298 SCIP_SEPADATA* sepadata, /**< separator data structure */
2299 SCIP_SOL* sol, /**< data structure to store an LP solution upon solving a Lagrangian dual problem with
2300 * fixed Lagrangian multipliers */
2301 SCIP_Real* solvals, /**< values of the LP solution obtained upon solving a Lagrangian dual problem with fixed
2302 * Lagrangian multipliers */
2303 int mainiternum, /**< iteration number of the outer loop of the relax-and-cut algorithm */
2304 SCIP_Real ubparam, /**< estimate of the optimal Lagrangian dual value */
2305 int depth, /**< depth of the current node in the tree */
2306 SCIP_Bool allowlocal, /**< should locally valid cuts be generated? */
2307 int nmaxgeneratedperroundcuts,/**< maximal number of cuts allowed to generate per separation round */
2308 SCIP_Real* origobjcoefs, /**< original objective function coefficients of the node linear relaxation */
2309 SCIP_Real origobjoffset, /**< original objective function offset of the node linear relaxation */
2310 SCIP_Real* dualvector, /**< Lagrangian multipliers vector */
2311 int* nsoftcuts, /**< number of generated cuts that were penalized and added to the Lagrangian dual problem */
2312 SCIP_ROW** generatedcurrroundcuts, /**< cuts generated in the current separation round */
2313 SCIP_Real* generatedcutefficacies, /**< array of generated cut efficacies w.r.t. the respective LP bases used for cut
2314 * generations */
2315 int* ngeneratedcutsperiter, /**< number of cuts generated per subgradient iteration in the current separation round */
2316 int* ngeneratedcurrroundcuts, /**< number of cuts generated so far in the current separation round */
2317 int* ncurrroundlpiters, /**< number of LP iterations taken for solving Lagrangian dual problems with fixed
2318 * multipliers in the current separator round */
2319 SCIP_Bool* cutoff, /**< should the current node be cutoff? */
2320 SCIP_Real* bestlagrangianval, /**< best Lagrangian value found so far */
2321 SCIP_Real* bestdualvector, /**< Lagrangian multipliers corresponding to the best Lagrangian value found so far */
2322 int* bestdualvectorlen, /**< length of the Lagrangian multipliers corresponding to the best Lagrangian value
2323 * found so far */
2324 int* nbestdualupdates, /**< number of best Lagrangian values found so far */
2325 int* totaliternum /**< total number of iterations of the relax-and-cut algorithm performed so far */
2326 )
2327{
2328 SCIP_Real* subgradient;
2329 SCIP_Real muparam;
2330 SCIP_Real steplength;
2331 SCIP_Real objval;
2332 SCIP_Real lagrangianval;
2333 SCIP_Real* lagrangianvals;
2334 SCIP_Real avglagrangianval;
2335 SCIP_Real maxsoftcutviol;
2336 SCIP_Real maxnzsubgradientdualprod;
2337 SCIP_Real maxviolscore;
2338 SCIP_Real maxviolscoreold;
2339 SCIP_Real nviolscore;
2340 SCIP_Real nviolscoreold;
2341 SCIP_Real scoreweight;
2342 SCIP_Real ballradius;
2343 SCIP_Bool solfound;
2344 SCIP_Bool backtrack;
2345 SCIP_Bool terminate;
2346 SCIP_Bool subgradientzero;
2347 SCIP_Bool objvecsdiffer;
2348 SCIP_Bool dualvecsdiffer;
2349 SCIP_Bool solvelp;
2350 int ncurrroundlpiterslast;
2351 int nlpiters;
2352 int nnewaddedsoftcuts;
2353 int nsoftcutviols;
2354 int nnzsubgradientdualprod;
2355 int i;
2356 int j;
2357
2358 SCIP_CALL( SCIPallocBufferArray(scip, &lagrangianvals, sepadata->nmaxsubgradientiters) );
2359 SCIP_CALL( SCIPallocCleanBufferArray(scip, &subgradient, nmaxgeneratedperroundcuts) );
2360
2361 muparam = sepadata->muparaminit;
2362 steplength = 0.0;
2363 objval = 0.0;
2364 avglagrangianval = 0.0;
2365 maxsoftcutviol = 0.0;
2366 maxnzsubgradientdualprod = 0.0;
2367 maxviolscore = 0.0;
2368 nviolscore = 0.0;
2369 scoreweight = 1.0;
2370 ballradius = sepadata->radiusinit;
2371 nsoftcutviols = 0;
2372 nnzsubgradientdualprod = 0;
2373 terminate = FALSE;
2374 objvecsdiffer = FALSE;
2375 solvelp = TRUE;
2376
2377 /* update objective vector based on input Lagrangian multipliers */
2378 if( *nsoftcuts > 0 )
2379 {
2380 SCIP_CALL( updateObjectiveVector(scip, dualvector, generatedcurrroundcuts, *nsoftcuts, origobjcoefs, &objvecsdiffer) );
2381 }
2382
2383 /* termination check */
2384 SCIP_CALL( checkLagrangianDualTermination(sepadata, -1, -1, FALSE, *ngeneratedcurrroundcuts,
2385 nmaxgeneratedperroundcuts, *ncurrroundlpiters, depth, &terminate) );
2386
2387 /* the subgradient algorithm loop */
2388 for( i = 0; i < sepadata->nmaxsubgradientiters && !SCIPisStopped(scip) && !terminate; i++ )
2389 {
2390 solfound = FALSE;
2391 subgradientzero = FALSE;
2392 objvecsdiffer = FALSE;
2393 dualvecsdiffer = FALSE;
2394 nnewaddedsoftcuts = 0;
2395 scoreweight *= sepadata->radiusupdateweight;
2396
2397 ncurrroundlpiterslast = *ncurrroundlpiters;
2398 if( solvelp )
2399 {
2400 /* solve Lagrangian dual for fixed Lagrangian multipliers */
2401 SCIP_CALL( solveLagromoryLP(scip, sepadata, depth, origobjoffset, &solfound, sol, solvals, &objval,
2402 ncurrroundlpiters) );
2403 }
2404 nlpiters = *ncurrroundlpiters - ncurrroundlpiterslast;
2405
2406 /* if an optimal solution has been found, then generate cuts and do other operations */
2407 if( solfound )
2408 {
2409 /* generate GMI cuts if a new basis solution is found */
2410 if( (nlpiters >= 1) && (i % sepadata->cutgenfreq == 0) )
2411 {
2412 int ngeneratednewcuts = 0;
2413 SCIP_CALL( generateGMICuts(scip, sepa, sepadata, mainiternum, i, sol, solvals,
2414 nmaxgeneratedperroundcuts, allowlocal, generatedcurrroundcuts, generatedcutefficacies,
2415 *ngeneratedcurrroundcuts, &ngeneratednewcuts, depth, cutoff));
2416 sepadata->ntotalcuts += ngeneratednewcuts;
2417 *ngeneratedcurrroundcuts += ngeneratednewcuts;
2418 ngeneratedcutsperiter[mainiternum * sepadata->nmaxsubgradientiters + i + 1] = ngeneratednewcuts;
2419 }
2420
2421 /* update subgradient, i.e., find the residuals of the penalized cuts, and determine various violations */
2422 updateSubgradient(scip, sol, generatedcurrroundcuts, *nsoftcuts, subgradient, dualvector, &subgradientzero,
2423 &nsoftcutviols, &maxsoftcutviol, &nnzsubgradientdualprod, &maxnzsubgradientdualprod);
2424
2425 /* calculate Lagrangian value for the fixed Lagrangian multipliers, and update best and avg values */
2426 updateLagrangianValue(scip, objval, dualvector, generatedcurrroundcuts, *nsoftcuts, &lagrangianval);
2427 if( SCIPisPositive(scip, lagrangianval - *bestlagrangianval) )
2428 {
2429 *bestlagrangianval = lagrangianval;
2430
2431 for( j = 0; j < *nsoftcuts; j++ )
2432 bestdualvector[j] = dualvector[j];
2433
2434 *bestdualvectorlen = *nsoftcuts;
2435 (*nbestdualupdates)++;
2436 }
2437 lagrangianvals[i] = lagrangianval;
2438 if( i < sepadata->nmaxlagrangianvalsforavg )
2439 avglagrangianval = (avglagrangianval * i + lagrangianval)/(i+1);
2440 else
2441 {
2442 avglagrangianval = (avglagrangianval * sepadata->nmaxlagrangianvalsforavg -
2443 lagrangianvals[i - sepadata->nmaxlagrangianvalsforavg] +
2444 lagrangianval)/(sepadata->nmaxlagrangianvalsforavg);
2445 }
2446
2447 /* if the subgradient vector is non-zero, then update the mu parameter and the Lagrangian multipliers */
2448 if( !subgradientzero )
2449 {
2450 /* update mu param */
2451 SCIP_CALL( updateMuSteplengthParam(scip, sepadata, i, ubparam, lagrangianvals, *bestlagrangianval, avglagrangianval,
2452 &muparam, &backtrack) );
2453
2454 /* update step length */
2455 updateStepLength(scip, muparam, ubparam, lagrangianval, subgradient, *nsoftcuts, &steplength);
2456
2457 /* update scores to determine how to update the stabilization ball radius */
2458 maxviolscoreold = maxviolscore;
2459 nviolscoreold = nviolscore;
2460 maxviolscore = (1.0 - scoreweight) * maxsoftcutviol + scoreweight * maxnzsubgradientdualprod;
2461 nviolscore = (1.0 - scoreweight) * nsoftcutviols + scoreweight * nnzsubgradientdualprod;
2462
2463 /* update Lagrangian multipliers */
2464 SCIP_CALL( updateDualVector(scip, sepadata, dualvector, bestdualvector, *bestdualvectorlen,
2465 *nbestdualupdates, i, *totaliternum, steplength, subgradient, *nsoftcuts, backtrack, maxviolscore,
2466 maxviolscoreold, nviolscore, nviolscoreold, nlpiters, &dualvecsdiffer, &ballradius) );
2467
2468 /* update objective vector based on updated Lagrangian multipliers */
2469 if( dualvecsdiffer )
2470 {
2471 SCIP_CALL( updateObjectiveVector(scip, dualvector, generatedcurrroundcuts, *nsoftcuts, origobjcoefs, &objvecsdiffer) );
2472 }
2473 }
2474 /* if the subgradient vector if zero, then simply mark that the Lagrangian multipliers and the objective
2475 * function of the Lagrangian dual did not change */
2476 else
2477 {
2478 dualvecsdiffer = FALSE;
2479 objvecsdiffer = FALSE;
2480 }
2481
2482 /* add generated GMI cuts to the objective function of the Lagrangian dual problem by introducing new
2483 * Lagrangian multipliers */
2484 if( (i % sepadata->cutaddfreq == 0) || (!dualvecsdiffer && !objvecsdiffer &&
2485 (*ngeneratedcurrroundcuts - *nsoftcuts > 0)) )
2486 {
2487 SCIP_CALL( addGMICutsAsSoftConss(dualvector, *ngeneratedcurrroundcuts, nsoftcuts, &nnewaddedsoftcuts) );
2488 }
2489 }
2490 else
2491 {
2492 /* add any remaining generated GMI cuts to the objective function of the Lagrangian dual problem by introducing
2493 * new Lagrangian multipliers */
2494 if( (*ngeneratedcurrroundcuts - *nsoftcuts) > 0 )
2495 {
2496 SCIP_CALL( addGMICutsAsSoftConss(dualvector, *ngeneratedcurrroundcuts, nsoftcuts, &nnewaddedsoftcuts) );
2497 }
2498
2499 solvelp = FALSE;
2500 }
2501
2502 /* termination check */
2503 SCIP_CALL( checkLagrangianDualTermination(sepadata, nnewaddedsoftcuts, *ngeneratedcurrroundcuts - *nsoftcuts,
2504 objvecsdiffer, *ngeneratedcurrroundcuts, nmaxgeneratedperroundcuts, *ncurrroundlpiters, depth,
2505 &terminate) );
2506
2507 (*totaliternum)++;
2508 }
2509
2510 /* add any remaining generated GMI cuts to the objective function of the Lagrangian dual problem by introducing new
2511 * Lagrangian multipliers */
2512 if( (*ngeneratedcurrroundcuts - *nsoftcuts) > 0 )
2513 {
2514 SCIP_CALL( addGMICutsAsSoftConss(dualvector, *ngeneratedcurrroundcuts, nsoftcuts, &nnewaddedsoftcuts) );
2515 }
2516
2517 /* free memory */
2518 for( i = 0; i < nmaxgeneratedperroundcuts; i++)
2519 subgradient[i] = 0.0;
2520
2521 SCIPfreeCleanBufferArray(scip, &subgradient);
2522 SCIPfreeBufferArray(scip, &lagrangianvals);
2523
2524 return SCIP_OKAY;
2525}
2526
2527/** generates initial cut pool before solving the Lagrangian dual */
2528static
2529SCIP_RETCODE generateInitCutPool(
2530 SCIP* scip, /**< SCIP data structure */
2531 SCIP_SEPA* sepa, /**< separator */
2532 SCIP_SEPADATA* sepadata, /**< separator data structure */
2533 int mainiternum, /**< iteration number of the outer loop of the relax-and-cut algorithm */
2534 SCIP_SOL* sol, /**< LP solution to be used for cut generation */
2535 SCIP_Real* solvals, /**< values of the LP solution to be used for cut generation */
2536 int nmaxgeneratedperroundcuts,/**< maximal number of cuts allowed to generate per separation round */
2537 SCIP_Bool allowlocal, /**< should locally valid cuts be generated? */
2538 SCIP_ROW** generatedcurrroundcuts, /**< cuts generated in the current separation round */
2539 SCIP_Real* generatedcutefficacies, /**< array of generated cut efficacies w.r.t. the respective LP bases used for cut
2540 * generations */
2541 int* ngeneratedcutsperiter, /**< number of cuts generated per subgradient iteration in the current separation round */
2542 int* ngeneratedcurrroundcuts, /**< number of cuts generated so far in the current separation round */
2543 int depth, /**< depth of the current node in the tree */
2544 SCIP_Bool* cutoff /**< should the current node be cutoff? */
2545 )
2546{
2547 int ngeneratednewcuts;
2548
2549 ngeneratednewcuts = 0;
2550
2551 /* generate initial set of cuts */
2552 SCIP_CALL( generateGMICuts(scip, sepa, sepadata, mainiternum, -1, sol, solvals, nmaxgeneratedperroundcuts,
2553 allowlocal, generatedcurrroundcuts, generatedcutefficacies, *ngeneratedcurrroundcuts, &ngeneratednewcuts,
2554 depth, cutoff) );
2555
2556 /* update certain statistics */
2557 sepadata->ntotalcuts += ngeneratednewcuts;
2558 *ngeneratedcurrroundcuts += ngeneratednewcuts;
2559 ngeneratedcutsperiter[sepadata->nmaxsubgradientiters * mainiternum] = ngeneratednewcuts;
2560
2561 return SCIP_OKAY;
2562}
2563
2564/** add cuts to SCIP */
2565static
2566SCIP_RETCODE addCuts(
2567 SCIP* scip, /**< SCIP data structure */
2568 SCIP_SEPADATA* sepadata, /**< separator data structure */
2569 SCIP_ROW** cuts, /**< cuts generated so far in the current separation round */
2570 int ncuts, /**< number of cuts generated so far in the current separation round */
2571 SCIP_Longint maxdnom, /**< maximum denominator in the rational representation of cuts */
2572 SCIP_Real maxscale, /**< maximal scale factor to scale the cuts to integral values */
2573 int* naddedcuts, /**< number of cuts added to either global cutpool or sepastore */
2574 SCIP_Bool* cutoff /**< should the current node be cutoff? */
2575 )
2576{
2577 SCIP_ROW* cut;
2578 SCIP_Bool madeintegral;
2579 int i;
2580
2581 assert(scip != NULL);
2582 assert(sepadata != NULL);
2583 assert(naddedcuts != NULL);
2584 assert(cutoff != NULL);
2585
2586 *cutoff = FALSE;
2587 madeintegral = FALSE;
2588
2589 for( i = 0; i < ncuts && !*cutoff; i++ )
2590 {
2591 cut = cuts[i];
2592
2593 if( SCIProwGetNNonz(cut) == 1 )
2594 {
2595 /* Add the bound change as cut to avoid that the LP gets modified. This would mean that the LP is not flushed
2596 * and the method SCIPgetLPBInvRow() fails; SCIP internally will apply this bound change automatically. */
2597 SCIP_CALL( SCIPaddRow(scip, cut, TRUE, cutoff) );
2598 ++(*naddedcuts);
2599 }
2600 else
2601 {
2602 if( sepadata->makeintegral && SCIPgetRowNumIntCols(scip, cut) == SCIProwGetNNonz(cut) )
2603 {
2604 /* try to scale the cut to integral values */
2605 SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
2606 maxdnom, maxscale, MAKECONTINTEGRAL, &madeintegral) );
2607
2608 /* if RHS = plus infinity (due to scaling), the cut is useless, so we are not adding it */
2609 if( madeintegral && SCIPisInfinity(scip, SCIProwGetRhs(cut)) )
2610 return SCIP_OKAY;
2611 }
2612
2613 if( SCIPisCutNew(scip, cut) )
2614 {
2615 /* add global cuts which are not implicit bound changes to the cut pool */
2616 if( !SCIProwIsLocal(cut) )
2617 {
2618 if( sepadata->delayedcuts )
2619 {
2620 SCIP_CALL( SCIPaddDelayedPoolCut(scip, cut) );
2621 }
2622 else
2623 {
2624 SCIP_CALL( SCIPaddPoolCut(scip, cut) );
2625 }
2626 }
2627 else
2628 {
2629 /* local cuts we add to the sepastore */
2630 SCIP_CALL( SCIPaddRow(scip, cut, sepadata->forcecuts, cutoff) );
2631 }
2632 ++(*naddedcuts);
2633 }
2634 }
2635 }
2636
2637 return SCIP_OKAY;
2638}
2639
2640/** check different termination criteria */
2641/* @todo nlpssolved criterion? */
2642static
2643SCIP_RETCODE checkMainLoopTermination(
2644 SCIP_SEPADATA* sepadata, /**< separator data structure */
2645 SCIP_Bool cutoff, /**< should the current node be cutoff? */
2646 SCIP_Bool dualvecsdiffer, /**< whether the updated Lagrangian multipliers differ from the old one */
2647 int ngeneratedcurrroundcuts, /**< number of cuts generated in the current separation round */
2648 int nsoftcuts, /**< number of generated cuts that were penalized and added to the Lagrangian dual problem */
2649 int nmaxgeneratedperroundcuts, /**< maximal number of cuts allowed to generate per separation round */
2650 int ncurrroundlpiters, /**< number of LP iterations taken for solving Lagrangian dual problems with fixed
2651 * multipliers in the current separator round */
2652 int depth, /**< depth of the current node in the tree */
2653 SCIP_Bool* terminate /**< whether to terminate the relax-and-cut algorithm */
2654 )
2655{
2656 *terminate = FALSE;
2657
2658 /* check if the node has been identified to be cutoff */
2659 if( cutoff )
2660 *terminate = TRUE;
2661
2662 /* check if the Lagrangian multipliers do not differ from the previous iteration and no new cuts exist for penalizing */
2663 if( !dualvecsdiffer && (ngeneratedcurrroundcuts == nsoftcuts) )
2664 *terminate = TRUE;
2665
2666 /* check if allowed number of cuts in this separation round have already been generated */
2667 if( ngeneratedcurrroundcuts >= nmaxgeneratedperroundcuts )
2668 *terminate = TRUE;
2669
2670 /* check if allowed number of cuts in the tree have already been generated */
2671 if( sepadata->ntotalcuts >= sepadata->nmaxtotalcuts )
2672 *terminate = TRUE;
2673
2674 /* check if allowed number of simplex iterations in this separation round have already been used up */
2675 if( (sepadata->nmaxperroundlpiters >= 0) && (ncurrroundlpiters >= sepadata->nmaxperroundlpiters) )
2676 *terminate = TRUE;
2677
2678 /* check if allowed number of simplex iterations in the root node have already been used up */
2679 if( (depth == 0) && (sepadata->nmaxrootlpiters >= 0) && (sepadata->nrootlpiters >= sepadata->nmaxrootlpiters) )
2680 *terminate = TRUE;
2681
2682 /* check if allowed number of simplex iterations in the tree have already been used up */
2683 if( (sepadata->nmaxtotallpiters >= 0) && (sepadata->ntotallpiters >= sepadata->nmaxtotallpiters) )
2684 *terminate = TRUE;
2685
2686 return SCIP_OKAY;
2687}
2688
2689/** searches and tries to add Lagromory cuts */
2690static
2691SCIP_RETCODE separateCuts(
2692 SCIP* scip, /**< SCIP data structure */
2693 SCIP_SEPA* sepa, /**< separator */
2694 SCIP_SEPADATA* sepadata, /**< separator data structure */
2695 SCIP_Real ubparam, /**< estimate of the optimal Lagrangian dual value */
2696 int depth, /**< depth of the current node in the tree */
2697 SCIP_Bool allowlocal, /**< should locally valid cuts be generated? */
2698 SCIP_RESULT* result /**< final result of the separation round */
2699 )
2700{
2701 SCIP_ROW** generatedcurrroundcuts;
2702 SCIP_ROW** aggregatedcurrroundcuts;
2703 SCIP_Real* generatedcutefficacies;
2704 SCIP_Bool solfound;
2705 SCIP_SOL* softcutslpsol;
2706 SCIP_Real* softcutslpsolvals;
2707 SCIP_SOL* hardcutslpsol;
2708 SCIP_Real* hardcutslpsolvals;
2709 SCIP_Real* dualsol;
2710 SCIP_Real* dualvector;
2711 SCIP_Real* bestdualvector;
2712 SCIP_Real bestlagrangianval;
2713 SCIP_Real* origobjcoefs;
2714 SCIP_Real origobjoffset;
2715 SCIP_Real objval;
2716 SCIP_Real maxscale;
2717 SCIP_Longint maxdnom;
2718 SCIP_Bool cutoff;
2719 SCIP_Bool cutoff2;
2720 SCIP_Bool dualvecsdiffer;
2721 SCIP_Bool terminate;
2722 SCIP_COL** cols;
2723
2724 int* ngeneratedcutsperiter;
2725 int bestdualvectorlen;
2726 int nbestdualupdates;
2727 int totaliternum;
2728 int* cutindsperm;
2729 int nprocessedcuts;
2730 int ncols;
2731 int nrows;
2732 int ngeneratedcurrroundcuts;
2733 int nselectedcurrroundcuts;
2734 int nselectedcuts;
2735 int naddedcurrroundcuts;
2736 int naggregatedcurrroundcuts;
2737 int nmaxgeneratedperroundcuts;
2738 int ncurrroundlpiters;
2739 int nsoftcuts;
2740 int nsoftcutsold;
2741 int maxdepth;
2742 int i;
2743 int j;
2744
2745 assert(*result == SCIP_DIDNOTRUN);
2746 assert(sepadata != NULL);
2747 sepadata->ncalls = SCIPsepaGetNCalls(sepa);
2748 objval = SCIPinfinity(scip);
2749 bestlagrangianval = -SCIPinfinity(scip);
2750 bestdualvectorlen = 0;
2751 nbestdualupdates = 0;
2752 totaliternum = 0;
2753 ngeneratedcurrroundcuts = 0;
2754 naddedcurrroundcuts = 0;
2755 naggregatedcurrroundcuts = 0;
2756 ncurrroundlpiters = 0;
2757 nsoftcuts = 0;
2758 solfound = FALSE;
2759 cutoff = FALSE;
2760 cutoff2 = FALSE;
2761 terminate = FALSE;
2762
2763 SCIPdebugMsg(scip, "Separating cuts...\n");
2764
2765 /* initialize the LP that will be used to solve the Lagrangian dual with fixed Lagrangian multipliers */
2766 SCIP_CALL( createLPWithSoftCuts(scip, sepadata) );
2767 /* create the LP that represents the node relaxation including all the generated cuts in this separator */
2768 SCIP_CALL( createLPWithHardCuts(scip, sepadata, NULL, 0) );
2769
2770 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
2771 nrows = SCIPgetNLPRows(scip);
2772
2773 /* get the maximal number of cuts allowed in a separation round */
2774 nmaxgeneratedperroundcuts = ((depth == 0) ? sepadata->nmaxperroundcutsroot : sepadata->nmaxperroundcuts);
2775
2776 /* allocate memory */
2777 SCIP_CALL( SCIPallocBufferArray(scip, &generatedcurrroundcuts, nmaxgeneratedperroundcuts) );
2778 SCIP_CALL( SCIPallocBufferArray(scip, &aggregatedcurrroundcuts, nmaxgeneratedperroundcuts) );
2779 SCIP_CALL( SCIPallocBufferArray(scip, &generatedcutefficacies, nmaxgeneratedperroundcuts) );
2780 SCIP_CALL( SCIPallocBufferArray(scip, &cutindsperm, nmaxgeneratedperroundcuts) );
2781 SCIP_CALL( SCIPallocCleanBufferArray(scip, &ngeneratedcutsperiter, sepadata->nmaxmainiters *
2782 (sepadata->nmaxsubgradientiters + 1)) );
2783 SCIP_CALL( SCIPallocCleanBufferArray(scip, &dualsol, nrows + nmaxgeneratedperroundcuts) );
2784 SCIP_CALL( SCIPallocCleanBufferArray(scip, &dualvector, nmaxgeneratedperroundcuts) );
2785 SCIP_CALL( SCIPallocCleanBufferArray(scip, &bestdualvector, nmaxgeneratedperroundcuts) );
2786 SCIP_CALL( SCIPallocBufferArray(scip, &softcutslpsolvals, ncols) );
2787 SCIP_CALL( SCIPcreateSol(scip, &softcutslpsol, NULL) );
2788 SCIP_CALL( SCIPallocBufferArray(scip, &hardcutslpsolvals, ncols) );
2789 SCIP_CALL( SCIPcreateSol(scip, &hardcutslpsol, NULL) );
2790 SCIP_CALL( SCIPallocBufferArray(scip, &origobjcoefs, ncols) );
2791
2792 /* store current objective function */
2793 for( i = 0; i < ncols; i++ )
2794 origobjcoefs[i] = SCIPcolGetObj(cols[i]);
2795
2796 origobjoffset = SCIPgetTransObjoffset(scip);
2797
2798 /* solve node LP relaxation to have an initial simplex tableau */
2799 SCIP_CALL( solveLagromoryLP(scip, sepadata, depth, origobjoffset, &solfound, softcutslpsol, softcutslpsolvals, &objval,
2800 &ncurrroundlpiters));
2801
2802 /* generate initial cut pool */
2803 SCIP_CALL( generateInitCutPool(scip, sepa, sepadata, 0, softcutslpsol, softcutslpsolvals, nmaxgeneratedperroundcuts, allowlocal,
2804 generatedcurrroundcuts, generatedcutefficacies, ngeneratedcutsperiter, &ngeneratedcurrroundcuts, depth,
2805 &cutoff) );
2806
2807 /* termination check */
2808 SCIP_CALL( checkMainLoopTermination(sepadata, cutoff, TRUE, ngeneratedcurrroundcuts, nsoftcuts,
2809 nmaxgeneratedperroundcuts, ncurrroundlpiters, depth, &terminate) );
2810
2811 /* compute cuts for each integer col with fractional val */
2812 for( i = 0; i < sepadata->nmaxmainiters && !SCIPisStopped(scip) && !terminate; ++i )
2813 {
2814 nsoftcutsold = nsoftcuts;
2815 nsoftcuts = ngeneratedcurrroundcuts;
2816 dualvecsdiffer = FALSE;
2817
2818 /* solve Lagrangain dual */
2819 SCIP_CALL( solveLagrangianDual(scip, sepa, sepadata, softcutslpsol, softcutslpsolvals, i, ubparam, depth, allowlocal,
2820 nmaxgeneratedperroundcuts, origobjcoefs, origobjoffset, dualvector, &nsoftcuts, generatedcurrroundcuts,
2821 generatedcutefficacies, ngeneratedcutsperiter, &ngeneratedcurrroundcuts, &ncurrroundlpiters, &cutoff,
2822 &bestlagrangianval, bestdualvector, &bestdualvectorlen, &nbestdualupdates, &totaliternum) );
2823
2824 /* @todo filter cuts before adding them to the new LP that was created based on the node relaxation? */
2825
2826 /* update the LP representing the node relaxation by adding newly generated cuts */
2827 if( !cutoff && (ngeneratedcurrroundcuts - nsoftcutsold > 0) )
2828 {
2829 SCIP_CALL( createLPWithHardCuts(scip, sepadata, generatedcurrroundcuts, ngeneratedcurrroundcuts) );
2830
2831 /* solve the LP and get relevant information */
2832 SCIP_CALL( solveLPWithHardCuts(scip, sepadata, &solfound, hardcutslpsol, hardcutslpsolvals) );
2833
2834 /* if primal solution is found, then pass it to trysol heuristic */
2835 /* @note if trysol heuristic is was not present, then the solution found above, which can potentially be a MIP
2836 * primal feasible solution, will go to waste.
2837 */
2838 if( solfound && sepadata->heurtrysol != NULL )
2839 {
2840 SCIP_CALL( SCIPheurPassSolTrySol(scip, sepadata->heurtrysol, hardcutslpsol) );
2841 }
2842
2843 /* if dual feasible, then fetch dual solution and reset Lagrangian multipliers based on it. otherwise, retain the
2844 * Lagrangian multipliers and simply initialize the new multipliers to zeroes. */
2845 if( SCIPlpiWasSolved(sepadata->lpiwithhardcuts) && SCIPlpiIsDualFeasible(sepadata->lpiwithhardcuts) )
2846 {
2847 SCIP_CALL( SCIPlpiGetSol(sepadata->lpiwithhardcuts, NULL, NULL, dualsol, NULL, NULL) );
2848 SCIP_CALL( updateDualVector(scip, sepadata, dualvector, &(dualsol[nrows]),
2849 ngeneratedcurrroundcuts, 0, -1, -1, 0.0, NULL, ngeneratedcurrroundcuts, TRUE, 0.0, 0.0, 0.0, 0.0, -1,
2850 &dualvecsdiffer, NULL) );
2851 }
2852 else
2853 {
2854 SCIP_CALL( updateDualVector(scip, sepadata, dualvector, dualvector, nsoftcuts, 0, -1, -1, 0.0, NULL,
2855 ngeneratedcurrroundcuts, TRUE, 0.0, 0.0, 0.0, 0.0, -1, &dualvecsdiffer, NULL) );
2856 }
2857 }
2858
2859 /* termination check */
2860 SCIP_CALL( checkMainLoopTermination(sepadata, cutoff, dualvecsdiffer, ngeneratedcurrroundcuts, nsoftcuts,
2861 nmaxgeneratedperroundcuts, ncurrroundlpiters, depth, &terminate) );
2862 }
2863
2864 /* set the maximal denominator in rational representation of gomory cut and the maximal scale factor to
2865 * scale resulting cut to integral values to avoid numerical instabilities
2866 */
2867 /* @todo find better but still stable gomory cut settings: look at dcmulti, gesa3, khb0525, misc06, p2756 */
2868 /* @note above todo was copied from sepa_gomory.c. So, if gomory code is changed, same changes can be done here. */
2869 maxdepth = SCIPgetMaxDepth(scip);
2870 if( depth == 0 )
2871 {
2872 maxdnom = 1000;
2873 maxscale = 1000.0;
2874 }
2875 else if( depth <= maxdepth/4 )
2876 {
2877 maxdnom = 1000;
2878 maxscale = 1000.0;
2879 }
2880 else if( depth <= maxdepth/2 )
2881 {
2882 maxdnom = 100;
2883 maxscale = 100.0;
2884 }
2885 else
2886 {
2887 maxdnom = 10;
2888 maxscale = 10.0;
2889 }
2890
2891 /* filter cuts by calling cut selection algorithms and add cuts accordingly */
2892 /* @todo an idea is to filter cuts after every main iter */
2893 /* @todo we can remove !cutoff criterion by adding forcedcuts */
2894 if( !cutoff && (ngeneratedcurrroundcuts > 0) )
2895 {
2896 if( SCIPisGE(scip, sepadata->cutsfilterfactor, 1.0) )
2897 {
2898 nselectedcurrroundcuts = ngeneratedcurrroundcuts;
2899 SCIP_CALL( addCuts(scip, sepadata, generatedcurrroundcuts, nselectedcurrroundcuts, maxdnom, maxscale,
2900 &naddedcurrroundcuts, &cutoff2) );
2901 cutoff = cutoff2;
2902 }
2903 else if( SCIPisPositive(scip, sepadata->cutsfilterfactor) )
2904 {
2905 nprocessedcuts = 0;
2906 for( i = 0; i < sepadata->nmaxmainiters * (sepadata->nmaxsubgradientiters + 1); i++ )
2907 {
2908 if( ngeneratedcutsperiter[i] != 0 )
2909 {
2910 for( j = 0; j < ngeneratedcutsperiter[i]; j++ )
2911 cutindsperm[j] = j + nprocessedcuts;
2912
2913 /* sort cut efficacies by fractionality */
2914 SCIPsortDownRealInt(&generatedcutefficacies[nprocessedcuts], cutindsperm, ngeneratedcutsperiter[i]);
2915
2916 nselectedcuts = (int)SCIPceil(scip, sepadata->cutsfilterfactor * ngeneratedcutsperiter[i]);
2917
2918 SCIP_CALL( addCuts(scip, sepadata, &generatedcurrroundcuts[nprocessedcuts], nselectedcuts, maxdnom,
2919 maxscale, &naddedcurrroundcuts, &cutoff2) );
2920 cutoff = cutoff2;
2921
2922 nprocessedcuts += ngeneratedcutsperiter[i];
2923 }
2924 }
2925 }
2926 }
2927 else if( ngeneratedcurrroundcuts > 0 )
2928 {
2929 nselectedcurrroundcuts = ngeneratedcurrroundcuts;
2930 SCIP_CALL( addCuts(scip, sepadata, generatedcurrroundcuts, nselectedcurrroundcuts, maxdnom, maxscale,
2931 &naddedcurrroundcuts, &cutoff2) );
2932 }
2933
2934 /* add an aggregated cut based on best Lagrangian multipliers */
2935 if( sepadata->aggregatecuts && (ngeneratedcurrroundcuts > 0) && (bestdualvectorlen > 0) )
2936 {
2937 assert(bestdualvectorlen <= ngeneratedcurrroundcuts);
2938 SCIP_CALL( aggregateGeneratedCuts(scip, sepa, sepadata, generatedcurrroundcuts, bestdualvector, bestdualvectorlen,
2939 aggregatedcurrroundcuts, &naggregatedcurrroundcuts, &cutoff2) );
2940 cutoff = (!cutoff ? cutoff2 : cutoff);
2941 if( naggregatedcurrroundcuts > 0 )
2942 {
2943 SCIP_CALL( addCuts(scip, sepadata, aggregatedcurrroundcuts, naggregatedcurrroundcuts, maxdnom, maxscale,
2944 &naddedcurrroundcuts, &cutoff2) );
2945 cutoff = (!cutoff ? cutoff2 : cutoff);
2946 }
2947 }
2948
2949 if( cutoff )
2950 {
2951 *result = SCIP_CUTOFF;
2952 }
2953 else if( naddedcurrroundcuts > 0 )
2954 {
2955 *result = SCIP_SEPARATED;
2956 }
2957 else
2958 {
2959 *result = SCIP_DIDNOTFIND;
2960 }
2961
2962 /* delete the LP representing the Lagrangian dual problem with fixed Lagrangian multipliers */
2963 SCIP_CALL( deleteLPWithSoftCuts(scip, sepadata) );
2964
2965 /* release the rows in aggregatedcurrroundcuts */
2966 for( i = 0; i < naggregatedcurrroundcuts; ++i )
2967 {
2968 SCIP_CALL( SCIPreleaseRow(scip, &(aggregatedcurrroundcuts[i])) );
2969 }
2970
2971 /* release the rows in generatedcurrroundcuts */
2972 for( i = 0; i < ngeneratedcurrroundcuts; ++i )
2973 {
2974 SCIP_CALL( SCIPreleaseRow(scip, &(generatedcurrroundcuts[i])) );
2975 }
2976
2977 for( i = 0; i < sepadata->nmaxmainiters * (sepadata->nmaxsubgradientiters + 1); i++ )
2978 ngeneratedcutsperiter[i] = 0;
2979
2980 for( i = 0; i < nrows; i++ )
2981 dualsol[i] = 0.0;
2982
2983 for( i = 0; i < nmaxgeneratedperroundcuts; i++ )
2984 {
2985 dualsol[nrows + i] = 0.0;
2986 dualvector[i] = 0.0;
2987 bestdualvector[i] = 0.0;
2988 }
2989
2990 /* free memory */
2991 SCIPfreeBufferArray(scip, &origobjcoefs);
2992 SCIPfreeBufferArray(scip, &hardcutslpsolvals);
2993 SCIP_CALL( SCIPfreeSol(scip, &hardcutslpsol) );
2994 SCIPfreeBufferArray(scip, &softcutslpsolvals);
2995 SCIP_CALL( SCIPfreeSol(scip, &softcutslpsol) );
2996 SCIPfreeCleanBufferArray(scip, &ngeneratedcutsperiter);
2997 SCIPfreeBufferArray(scip, &cutindsperm);
2998 SCIPfreeBufferArray(scip, &generatedcutefficacies);
2999 SCIPfreeBufferArray(scip, &aggregatedcurrroundcuts);
3000 SCIPfreeBufferArray(scip, &generatedcurrroundcuts);
3001 SCIPfreeCleanBufferArray(scip, &dualvector);
3002 SCIPfreeCleanBufferArray(scip, &bestdualvector);
3003 SCIPfreeCleanBufferArray(scip, &dualsol);
3004
3005 return SCIP_OKAY;
3006}
3007
3008/** creates separator data */
3009static
3010SCIP_RETCODE sepadataCreate(
3011 SCIP* scip, /**< SCIP data structure */
3012 SCIP_SEPADATA** sepadata /**< separator data structure */
3013 )
3014{
3015 assert(scip != NULL);
3016 assert(sepadata != NULL);
3017
3018 SCIP_CALL( SCIPallocBlockMemory(scip, sepadata) );
3019 BMSclearMemory(*sepadata);
3020
3021 return SCIP_OKAY;
3022}
3023
3024
3025/*
3026 * Callback methods of separator
3027 */
3028
3029/** copy method for separator plugins (called when SCIP copies plugins) */
3030static
3031SCIP_DECL_SEPACOPY(sepaCopyLagromory)
3032{ /*lint --e{715}*/
3033 assert(scip != NULL);
3034 assert(sepa != NULL);
3035 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3036
3037 /* call inclusion method of constraint handler */
3038 SCIP_CALL( SCIPincludeSepaLagromory(scip) );
3039
3040 return SCIP_OKAY;
3041}
3042
3043
3044/** destructor of separator to free user data (called when SCIP is exiting) */
3045static
3046SCIP_DECL_SEPAFREE(sepaFreeLagromory)
3047{
3048 SCIP_SEPADATA* sepadata;
3049
3050 sepadata = SCIPsepaGetData(sepa);
3051 assert(sepadata != NULL);
3052
3053 SCIP_CALL( sepadataFree(scip, &sepadata) );
3054 SCIPsepaSetData(sepa, NULL);
3055
3056 return SCIP_OKAY;
3057}
3058
3059
3060/** initialization method of separator (called after problem was transformed) */
3061static
3062SCIP_DECL_SEPAINIT(sepaInitLagromory)
3063{
3064 SCIP_SEPADATA* sepadata;
3065
3066 sepadata = SCIPsepaGetData(sepa);
3067 assert(scip != NULL);
3068 assert(sepadata != NULL);
3069
3070 /* create and initialize random number generator */
3071 SCIP_CALL( SCIPcreateRandom(scip, &(sepadata->randnumgen), RANDSEED, TRUE) );
3072
3073 /* find trysol heuristic */
3074 if ( sepadata->heurtrysol == NULL )
3075 sepadata->heurtrysol = SCIPfindHeur(scip, "trysol");
3076
3077 return SCIP_OKAY;
3078}
3079
3080/** deinitialization method of separator (called before transformed problem is freed) */
3081static
3082SCIP_DECL_SEPAEXIT(sepaExitLagromory)
3083{ /*lint --e{715}*/
3084 SCIP_SEPADATA* sepadata;
3085
3086 sepadata = SCIPsepaGetData(sepa);
3087 assert(sepadata != NULL);
3088
3089 SCIPfreeRandom(scip, &(sepadata->randnumgen));
3090
3091 return SCIP_OKAY;
3092}
3093
3094/** LP solution separation method of separator */
3095static
3096SCIP_DECL_SEPAEXECLP(sepaExeclpLagromory)
3097{
3098 /*lint --e{715}*/
3099
3100 SCIP_SEPADATA* sepadata;
3101 SCIP_SOL* bestsol;
3102 SCIP_COL** cols;
3103 SCIP_COL* col;
3104 SCIP_VAR* var;
3105 SCIP_Real ubparam;
3106 SCIP_Real dualdegeneracyrate;
3107 SCIP_Real varconsratio;
3108 SCIP_Real threshold1;
3109 SCIP_Real threshold2;
3110 int nrows;
3111 int ncols;
3112 int ncalls;
3113 int runnum;
3114 int i;
3115
3116 assert(sepa != NULL);
3117 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3118 sepadata = SCIPsepaGetData(sepa);
3119 assert(sepadata != NULL);
3120
3121 assert(result != NULL);
3122 *result = SCIP_DIDNOTRUN;
3123
3124 assert(scip != NULL);
3125
3126 ncalls = SCIPsepaGetNCallsAtNode(sepa);
3127 runnum = SCIPgetNRuns(scip);
3128 dualdegeneracyrate = 0.0;
3129 varconsratio = 0.0;
3130
3131 /* only generate Lagromory cuts if we are not close to terminating */
3132 if( SCIPisStopped(scip) )
3133 return SCIP_OKAY;
3134
3135 /* only call the separator starting sepadata->minrestart runs */
3136 if( (sepadata->minrestart >= 1) && (runnum < sepadata->minrestart + 1) )
3137 return SCIP_OKAY;
3138
3139 /* only call the separator a given number of times at each node */
3140 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
3141 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
3142 return SCIP_OKAY;
3143
3144 /* only generate cuts if an optimal LP solution is at hand */
3145 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
3146 return SCIP_OKAY;
3147
3148 /* only generate cuts if the LP solution is basic */
3149 if( ! SCIPisLPSolBasic(scip) )
3150 return SCIP_OKAY;
3151
3152 /* get LP data */
3153 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
3154 assert(cols != NULL);
3155
3156 nrows = SCIPgetNLPRows(scip);
3157
3158 /* return if LP has no columns or no rows */
3159 if( ncols == 0 || nrows == 0 )
3160 return SCIP_OKAY;
3161
3162 /* return if dual degeneracy metrics are below threshold values */
3163 threshold1 = sepadata->dualdegeneracyratethreshold;
3164 threshold2 = sepadata->varconsratiothreshold;
3165 SCIP_CALL( SCIPgetLPDualDegeneracy(scip, &dualdegeneracyrate, &varconsratio) );
3166 if( (dualdegeneracyrate < threshold1) && (varconsratio < threshold2) )
3167 return SCIP_OKAY;
3168
3169 bestsol = SCIPgetBestSol(scip);
3170 ubparam = 0.0;
3171
3172 /* if a MIP primal solution exists, use it to estimate the optimal value of the Lagrangian dual problem */
3173 if( bestsol != NULL )
3174 {
3175 for( i = 0; i < ncols; ++i )
3176 {
3177 col = cols[i];
3178 assert(col != NULL);
3179
3180 var = SCIPcolGetVar(col);
3181
3182 ubparam += SCIPgetSolVal(scip, bestsol, var) * SCIPcolGetObj(col);
3183 }
3184
3185 ubparam += SCIPgetTransObjoffset(scip);
3186 }
3187 /* if a MIP primal solution does not exist, then use the node relaxation's LP solutin to estimate the optimal value
3188 * of the Lagrangian dual problem
3189 */
3190 else
3191 {
3192 for( i = 0; i < ncols; ++i )
3193 {
3194 col = cols[i];
3195 assert(col != NULL);
3196
3197 ubparam += SCIPcolGetPrimsol(col) * SCIPcolGetObj(col);
3198 }
3199
3200 ubparam += SCIPgetTransObjoffset(scip);
3201 ubparam *= SCIPisPositive(scip, ubparam) ? sepadata->ubparamposfactor : sepadata->ubparamnegfactor;
3202 }
3203
3204 /* the main separation function of the separator */
3205 SCIP_CALL( separateCuts(scip, sepa, sepadata, ubparam, depth, (allowlocal && sepadata->allowlocal), result) );
3206
3207 return SCIP_OKAY;
3208}
3209
3210
3211/*
3212 * separator specific interface methods
3213 */
3214
3215/** creates the Lagromory separator and includes it in SCIP */
3216SCIP_RETCODE SCIPincludeSepaLagromory(
3217 SCIP* scip /**< SCIP data structure */
3218 )
3219{
3220 SCIP_SEPADATA* sepadata;
3221 SCIP_SEPA* sepa;
3222
3223 /* create separator data */
3224 SCIP_CALL( sepadataCreate(scip, &sepadata) );
3225
3226 sepadata->heurtrysol = NULL;
3227
3228 /* include separator */
3229 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
3230 SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpLagromory, NULL, sepadata) );
3231
3232 assert(sepa != NULL);
3233
3234 /* set non fundamental callbacks via setter functions */
3235 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyLagromory) );
3236 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeLagromory) );
3237 SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitLagromory) );
3238 SCIP_CALL( SCIPsetSepaExit(scip, sepa, sepaExitLagromory) );
3239
3240 /* add separator parameters */
3241 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/away", "minimal integrality violation of a basis "
3242 "variable to try separation", &sepadata->away, FALSE, DEFAULT_AWAY, 0.0, 1.0, NULL, NULL) );
3243
3244 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/rootlpiterlimitfactor", "factor w.r.t. root node LP "
3245 "iterations for maximal separating LP iterations in the root node (negative for no limit)",
3246 &sepadata->rootlpiterlimitfactor, TRUE, DEFAULT_ROOTLPITERLIMITFACTOR, -1.0, SCIP_REAL_MAX, NULL, NULL) );
3247
3248 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/totallpiterlimitfactor", "factor w.r.t. root node LP "
3249 "iterations for maximal separating LP iterations in the tree (negative for no limit)",
3250 &sepadata->totallpiterlimitfactor, TRUE, DEFAULT_TOTALLPITERLIMITFACTOR, -1.0, SCIP_REAL_MAX, NULL, NULL) );
3251
3252 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/perroundlpiterlimitfactor", "factor w.r.t. root node LP "
3253 "iterations for maximal separating LP iterations per separation round (negative for no limit)",
3254 &sepadata->perroundlpiterlimitfactor, TRUE, DEFAULT_PERROUNDLPITERLIMITFACTOR, -1.0, SCIP_REAL_MAX, NULL,
3255 NULL) );
3256
3257 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/perroundcutsfactorroot", "factor w.r.t. number of integer "
3258 "columns for number of cuts separated per separation round in root node", &sepadata->perroundcutsfactorroot,
3259 TRUE, DEFAULT_PERROUNDCUTSFACTORROOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3260
3261 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/perroundcutsfactor", "factor w.r.t. number of integer "
3262 "columns for number of cuts separated per separation round at a non-root node",
3263 &sepadata->perroundcutsfactor, TRUE, DEFAULT_PERROUNDCUTSFACTOR, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3264
3265 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/totalcutsfactor", "factor w.r.t. number of integer "
3266 "columns for total number of cuts separated", &sepadata->totalcutsfactor, TRUE, DEFAULT_TOTALCUTSFACTOR, 0.0,
3267 SCIP_REAL_MAX, NULL, NULL) );
3268
3269 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muparaminit", "initial value of the mu parameter (factor "
3270 "for step length)", &sepadata->muparaminit, TRUE, DEFAULT_MUPARAMINIT, 0.0, 100.0, NULL, NULL) );
3271
3272 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muparamlb", "lower bound of the mu parameter (factor for "
3273 "step length)", &sepadata->muparamlb, TRUE, DEFAULT_MUPARAMLB, 0.0, 1.0, NULL, NULL) );
3274
3275 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muparamub", "upper bound of the mu parameter (factor for "
3276 "step length)", &sepadata->muparamub, TRUE, DEFAULT_MUPARAMUB, 1.0, 10.0, NULL, NULL) );
3277
3278 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/mubacktrackfactor", "factor of mu while backtracking the "
3279 "mu parameter (factor for step length)", &sepadata->mubacktrackfactor, TRUE, DEFAULT_MUBACKTRACKFACTOR,
3280 0.0, 1.0, NULL, NULL) );
3281
3282 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muslab1factor", "factor of mu parameter (factor for step "
3283 "length) for larger increment" , &sepadata->muslab1factor, TRUE, DEFAULT_MUSLAB1FACTOR, 0.0, SCIP_REAL_MAX, NULL,
3284 NULL));
3285
3286 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muslab2factor", "factor of mu parameter (factor for step "
3287 "length) for smaller increment", &sepadata->muslab2factor, TRUE, DEFAULT_MUSLAB2FACTOR, 0.0, SCIP_REAL_MAX, NULL,
3288 NULL) );
3289
3290 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/muslab3factor", "factor of mu parameter (factor for step "
3291 "length) for reduction", &sepadata->muslab3factor, TRUE, DEFAULT_MUSLAB3FACTOR, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3292
3293 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/deltaslab1ub", "factor of delta deciding larger increment "
3294 "of mu parameter (factor for step length)", &sepadata->deltaslab1ub, TRUE, DEFAULT_DELTASLAB1UB, 0.0, 1.0,
3295 NULL, NULL) );
3296
3297 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/deltaslab2ub", "factor of delta deciding smaller "
3298 "increment of mu parameter (factor for step length)", &sepadata->deltaslab2ub, TRUE, DEFAULT_DELTASLAB2UB,
3299 0.0, 1.0, NULL, NULL) );
3300
3301 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/ubparamposfactor", "factor for positive upper bound used "
3302 "as an estimate for the optimal Lagrangian dual value", &sepadata->ubparamposfactor, TRUE, DEFAULT_UBPARAMPOSFACTOR,
3303 1.0, 100.0, NULL, NULL) );
3304
3305 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/ubparamnegfactor", "factor for negative upper bound used "
3306 "as an estimate for the optimal Lagrangian dual value", &sepadata->ubparamnegfactor, TRUE, DEFAULT_UBPARAMNEGFACTOR,
3307 0.0, 1.0, NULL, NULL) );
3308
3309 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/perrootlpiterfactor", "factor w.r.t. root node LP "
3310 "iterations for iteration limit of each separating LP (negative for no limit)",
3311 &sepadata->perrootlpiterfactor, TRUE, DEFAULT_PERROOTLPITERFACTOR, -1.0, SCIP_REAL_MAX, NULL, NULL) );
3312
3313 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/perlpiterfactor", "factor w.r.t. non-root node LP "
3314 "iterations for iteration limit of each separating LP (negative for no limit)", &sepadata->perlpiterfactor, TRUE,
3315 DEFAULT_PERLPITERFACTOR, -1.0, SCIP_REAL_MAX, NULL, NULL) );
3316
3317 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/cutsfilterfactor", "fraction of generated cuts per "
3318 "explored basis to accept from separator", &sepadata->cutsfilterfactor, TRUE, DEFAULT_CUTSFILTERFACTOR, 0.0,
3319 1.0, NULL, NULL) );
3320
3321 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/radiusinit", "initial radius of the ball used in "
3322 "stabilization of Lagrangian multipliers", &sepadata->radiusinit, TRUE, DEFAULT_RADIUSINIT, 0.0, 1.0, NULL,
3323 NULL) );
3324
3325 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/radiusmax", "maximum radius of the ball used in "
3326 "stabilization of Lagrangian multipliers", &sepadata->radiusmax, TRUE, DEFAULT_RADIUSMAX, 0.0, SCIP_REAL_MAX,
3327 NULL, NULL) );
3328
3329 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/radiusmin", "minimum radius of the ball used in "
3330 "stabilization of Lagrangian multipliers", &sepadata->radiusmin, TRUE, DEFAULT_RADIUSMIN, 0.0, SCIP_REAL_MAX,
3331 NULL, NULL) );
3332
3333 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/constant", "a constant for stablity center based "
3334 "stabilization of Lagrangian multipliers", &sepadata->constant, TRUE, DEFAULT_CONST, 2.0, SCIP_REAL_MAX,
3335 NULL, NULL) );
3336
3337 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/radiusupdateweight", "multiplier to evaluate cut "
3338 "violation score used for updating ball radius", &sepadata->radiusupdateweight, TRUE,
3339 DEFAULT_RADIUSUPDATEWEIGHT, 0.0, 1.0, NULL, NULL) );
3340
3341 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/dualdegeneracyratethreshold", "minimum dual degeneracy "
3342 "rate for separator execution", &sepadata->dualdegeneracyratethreshold, FALSE,
3343 DEFAULT_DUALDEGENERACYRATETHRESHOLD, 0.0, 1.0, NULL, NULL) );
3344
3345 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/varconsratiothreshold", "minimum variable-constraint "
3346 "ratio on optimal face for separator execution", &sepadata->varconsratiothreshold, FALSE,
3347 DEFAULT_VARCONSRATIOTHRESHOLD, 1.0, SCIP_REAL_MAX, NULL, NULL) );
3348
3349 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/muparamconst", "is the mu parameter (factor for step "
3350 "length) constant?" , &sepadata->muparamconst, TRUE, DEFAULT_MUPARAMCONST, NULL, NULL) );
3351
3352 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/separaterows", "separate rows with integral slack?",
3353 &sepadata->separaterows, TRUE, DEFAULT_SEPARATEROWS, NULL, NULL) );
3354
3355 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/sortcutoffsol", "sort fractional integer columns"
3356 "based on fractionality?" , &sepadata->sortcutoffsol, TRUE, DEFAULT_SORTCUTOFFSOL, NULL, NULL) );
3357
3358 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/sidetypebasis", "choose side types of row (lhs/rhs) "
3359 "based on basis information?", &sepadata->sidetypebasis, TRUE, DEFAULT_SIDETYPEBASIS, NULL, NULL) );
3360
3361 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/dynamiccuts", "should generated cuts be removed from "
3362 "LP if they are no longer tight?", &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
3363
3364 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/makeintegral", "try to scale all cuts to integral "
3365 "coefficients?", &sepadata->makeintegral, TRUE, DEFAULT_MAKEINTEGRAL, NULL, NULL) );
3366
3367 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/forcecuts", "force cuts to be added to the LP?",
3368 &sepadata->forcecuts, TRUE, DEFAULT_FORCECUTS, NULL, NULL) );
3369
3370 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/delayedcuts", "should cuts be added to the delayed cut "
3371 "pool", &sepadata->delayedcuts, TRUE, DEFAULT_DELAYEDCUTS, NULL, NULL) );
3372
3373 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/allowlocal", "should locally valid cuts be generated?",
3374 &sepadata->allowlocal, TRUE, DEFAULT_ALLOWLOCAL, NULL, NULL) );
3375
3376 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/aggregatecuts", "aggregate all generated cuts using the "
3377 "Lagrangian multipliers?", &sepadata->aggregatecuts, TRUE, DEFAULT_AGGREGATECUTS, NULL, NULL) );
3378
3379 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxrounds", "maximal number of separation rounds per node "
3380 "(-1: unlimited)", &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
3381
3382 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxroundsroot", "maximal number of separation rounds in "
3383 "the root node (-1: unlimited)", &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL,
3384 NULL) );
3385
3386 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/perroundnmaxlpiters", "maximal number of separating LP "
3387 "iterations per separation round (-1: unlimited)", &sepadata->perroundnmaxlpiters, FALSE,
3388 DEFAULT_PERROUNDMAXLPITERS, -1, INT_MAX, NULL, NULL) );
3389
3390 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxcutsperlp", "maximal number of cuts separated per "
3391 "Lagromory LP in the non-root node", &sepadata->nmaxcutsperlp, FALSE, DEFAULT_PERLPMAXCUTS, 0, INT_MAX, NULL,
3392 NULL) );
3393
3394 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxcutsperlproot", "maximal number of cuts separated per "
3395 "Lagromory LP in the root node", &sepadata->nmaxcutsperlproot, FALSE, DEFAULT_PERLPMAXCUTSROOT, 0, INT_MAX,
3396 NULL, NULL) );
3397
3398 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxmainiters", "maximal number of main loop iterations of "
3399 "the relax-and-cut algorithm", &sepadata->nmaxmainiters, TRUE, DEFAULT_MAXMAINITERS, 0, INT_MAX, NULL, NULL) );
3400
3401 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxsubgradientiters", "maximal number of subgradient loop "
3402 "iterations of the relax-and-cut algorithm", &sepadata->nmaxsubgradientiters, TRUE,
3403 DEFAULT_MAXSUBGRADIENTITERS, 0, INT_MAX, NULL, NULL) );
3404
3405 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/cutgenfreq", "frequency of subgradient iterations for "
3406 "generating cuts", &sepadata->cutgenfreq, TRUE, DEFAULT_CUTGENFREQ, 0, INT_MAX, NULL, NULL) );
3407
3408 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/cutaddfreq", "frequency of subgradient iterations for "
3409 "adding cuts to objective function", &sepadata->cutaddfreq, TRUE, DEFAULT_CUTADDFREQ, 0, INT_MAX, NULL, NULL) );
3410
3411 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxlagrangianvalsforavg", "maximal number of iterations "
3412 "for rolling average of Lagrangian value", &sepadata->nmaxlagrangianvalsforavg, TRUE,
3413 DEFAULT_MAXLAGRANGIANVALSFORAVG, 0, INT_MAX, NULL, NULL) );
3414
3415 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nmaxconsecitersformuupdate", "consecutive number of "
3416 "iterations used to determine if mu needs to be backtracked", &sepadata->nmaxconsecitersformuupdate, TRUE,
3417 DEFAULT_MAXCONSECITERSFORMUUPDATE, 0, INT_MAX, NULL, NULL) );
3418
3419 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/projectiontype", "the ball into which the Lagrangian multipliers "
3420 "are projected for stabilization (0: no projection, 1: L1-norm ball projection, 2: L2-norm ball projection, 3: "
3421 "L_inf-norm ball projection)", &sepadata->projectiontype, TRUE, DEFAULT_PROJECTIONTYPE, 0, 3, NULL, NULL));
3422
3423 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/stabilitycentertype", "type of stability center for "
3424 "taking weighted average of Lagrangian multipliers for stabilization (0: no weighted stabilization, 1: best "
3425 "Lagrangian multipliers)", &sepadata->stabilitycentertype, TRUE, DEFAULT_STABILITYCENTERTYPE, 0, 1, NULL,
3426 NULL) );
3427
3428 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/optimalfacepriority", "priority of the optimal face for "
3429 "separator execution (0: low priority, 1: medium priority, 2: high priority)",
3430 &sepadata->optimalfacepriority, TRUE, DEFAULT_OPTIMALFACEPRIORITY, 0, 2, NULL, NULL) );
3431
3432 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/minrestart", "minimum restart round for separator "
3433 "execution (0: from beginning of the instance solving, >= n with n >= 1: from restart round n)",
3434 &sepadata->minrestart, TRUE, DEFAULT_MINRESTART, 0, INT_MAX, NULL, NULL) );
3435
3436 return SCIP_OKAY;
3437}
BOUNDSWITCH
#define BOUNDSWITCH
Definition conflict_dualproofanalysis.c:83
POSTPROCESS
#define POSTPROCESS
Definition conflict_dualproofanalysis.c:84
USEVBDS
#define USEVBDS
Definition conflict_dualproofanalysis.c:85
DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDSROOT
Definition cons_knapsack.c:117
DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS
Definition cons_knapsack.c:116
RANDSEED
#define RANDSEED
Definition cutsel_dynamic.c:47
QUAD_ARRAY_STORE
#define QUAD_ARRAY_STORE(a, idx, x)
Definition dbldblarith.h:55
SCIPquadprecProdDD
#define SCIPquadprecProdDD(r, a, b)
Definition dbldblarith.h:58
QUAD_ARRAY_SIZE
#define QUAD_ARRAY_SIZE(size)
Definition dbldblarith.h:53
QUAD_ASSIGN
#define QUAD_ASSIGN(a, constant)
Definition dbldblarith.h:51
QUAD
#define QUAD(x)
Definition dbldblarith.h:47
SCIPquadprecSumQQ
#define SCIPquadprecSumQQ(r, a, b)
Definition dbldblarith.h:67
QUAD_ARRAY_LOAD
#define QUAD_ARRAY_LOAD(r, a, idx)
Definition dbldblarith.h:54
QUAD_TO_DBL
#define QUAD_TO_DBL(x)
Definition dbldblarith.h:49
NULL
#define NULL
Definition def.h:262
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition def.h:283
SCIP_Longint
#define SCIP_Longint
Definition def.h:157
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition def.h:173
SCIP_Bool
#define SCIP_Bool
Definition def.h:91
MIN
#define MIN(x, y)
Definition def.h:238
SCIP_Real
#define SCIP_Real
Definition def.h:172
SQR
#define SQR(x)
Definition def.h:213
TRUE
#define TRUE
Definition def.h:93
FALSE
#define FALSE
Definition def.h:94
MAX
#define MAX(x, y)
Definition def.h:234
SCIP_LONGINT_FORMAT
#define SCIP_LONGINT_FORMAT
Definition def.h:164
REALABS
#define REALABS(x)
Definition def.h:196
SCIP_CALL
#define SCIP_CALL(x)
Definition def.h:369
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition scip_general.c:734
SCIPgetTransObjoffset
SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
Definition scip_prob.c:1367
SCIPlpiSetState
SCIP_RETCODE SCIPlpiSetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, const SCIP_LPISTATE *lpistate)
Definition lpi_clp.cpp:3457
SCIPlpiInfinity
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
Definition lpi_clp.cpp:3947
SCIPlpiAddRows
SCIP_RETCODE SCIPlpiAddRows(SCIP_LPI *lpi, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
Definition lpi_clp.cpp:920
SCIPlpiSetRealpar
SCIP_RETCODE SCIPlpiSetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real dval)
Definition lpi_clp.cpp:3861
SCIPlpiFree
SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
Definition lpi_clp.cpp:643
SCIPlpiIsPrimalFeasible
SCIP_Bool SCIPlpiIsPrimalFeasible(SCIP_LPI *lpi)
Definition lpi_clp.cpp:2549
SCIPlpiIsDualFeasible
SCIP_Bool SCIPlpiIsDualFeasible(SCIP_LPI *lpi)
Definition lpi_clp.cpp:2637
SCIPlpiWasSolved
SCIP_Bool SCIPlpiWasSolved(SCIP_LPI *lpi)
Definition lpi_clp.cpp:2414
SCIPlpiGetSol
SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
Definition lpi_clp.cpp:2816
SCIPlpiFreeState
SCIP_RETCODE SCIPlpiFreeState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
Definition lpi_clp.cpp:3531
SCIPlpiAddCols
SCIP_RETCODE SCIPlpiAddCols(SCIP_LPI *lpi, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
Definition lpi_clp.cpp:758
SCIPlpiSolvePrimal
SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
Definition lpi_clp.cpp:1833
SCIPlpiCreate
SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
Definition lpi_clp.cpp:531
SCIPlpiGetState
SCIP_RETCODE SCIPlpiGetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
Definition lpi_clp.cpp:3417
SCIPgetMessagehdlr
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition scip_message.c:88
SCIPdebugMsg
#define SCIPdebugMsg
Definition scip_message.h:78
SCIPheurPassSolTrySol
SCIP_RETCODE SCIPheurPassSolTrySol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition heur_trysol.c:252
SCIPaddIntParam
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
SCIPaddRealParam
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:139
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
SCIPcolGetLPPos
int SCIPcolGetLPPos(SCIP_COL *col)
Definition lp.c:17122
SCIPcolGetVar
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition lp.c:17071
SCIPcolIsIntegral
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition lp.c:17101
SCIPcolGetObj
SCIP_Real SCIPcolGetObj(SCIP_COL *col)
Definition lp.c:16982
SCIPcolGetLb
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition lp.c:16992
SCIPcolGetPrimsol
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition lp.c:17025
SCIPcolGetUb
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition lp.c:17002
SCIPaddPoolCut
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition scip_cut.c:361
SCIPaggrRowCreate
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition cuts.c:1723
SCIPisCutNew
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
Definition scip_cut.c:343
SCIPisEfficacious
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition scip_cut.c:135
SCIPaggrRowFree
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition cuts.c:1755
SCIPaddRow
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition scip_cut.c:250
SCIPaggrRowSumRows
SCIP_RETCODE SCIPaggrRowSumRows(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid)
Definition cuts.c:2279
SCIPaddDelayedPoolCut
SCIP_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
Definition scip_cut.c:641
SCIPcalcMIR
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition cuts.c:3873
SCIPfindHeur
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition scip_heur.c:263
SCIPgetVarObjDive
SCIP_Real SCIPgetVarObjDive(SCIP *scip, SCIP_VAR *var)
Definition scip_lp.c:2591
SCIPstartDive
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition scip_lp.c:2246
SCIPgetLPDualDegeneracy
SCIP_RETCODE SCIPgetLPDualDegeneracy(SCIP *scip, SCIP_Real *degeneracy, SCIP_Real *varconsratio)
Definition scip_lp.c:2796
SCIPchgVarObjDive
SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition scip_lp.c:2382
SCIPsolveDiveLP
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition scip_lp.c:2682
SCIPgetLPBasisInd
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition scip_lp.c:687
SCIPgetLPColsData
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition scip_lp.c:472
SCIPgetLPRowsData
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition scip_lp.c:571
SCIPgetNLPRows
int SCIPgetNLPRows(SCIP *scip)
Definition scip_lp.c:627
SCIPgetLPI
SCIP_RETCODE SCIPgetLPI(SCIP *scip, SCIP_LPI **lpi)
Definition scip_lp.c:989
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:169
SCIPgetLPCols
SCIP_COL ** SCIPgetLPCols(SCIP *scip)
Definition scip_lp.c:507
SCIPgetLPObjval
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition scip_lp.c:248
SCIPisLPSolBasic
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition scip_lp.c:668
SCIPgetLPBInvRow
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition scip_lp.c:715
SCIPfreeCleanBufferArray
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition scip_mem.h:146
SCIPallocCleanBufferArray
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition scip_mem.h:142
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIProwIsIntegral
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition lp.c:17420
SCIProwGetLhs
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition lp.c:17321
SCIProwIsModifiable
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition lp.c:17440
SCIPcacheRowExtensions
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1639
SCIPgetRowMinActivity
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1943
SCIProwGetNNonz
int SCIProwGetNNonz(SCIP_ROW *row)
Definition lp.c:17242
SCIProwGetCols
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition lp.c:17267
SCIProwGetRhs
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition lp.c:17331
SCIPgetRowMaxActivity
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1960
SCIProwGetNLPNonz
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition lp.c:17256
SCIPflushRowExtensions
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1662
SCIProwIsLocal
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition lp.c:17430
SCIPmakeRowIntegral
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
Definition scip_lp.c:1848
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition scip_lp.c:1705
SCIProwGetName
const char * SCIProwGetName(SCIP_ROW *row)
Definition lp.c:17380
SCIPgetRowActivity
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:2108
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1566
SCIPcreateEmptyRowSepa
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition scip_lp.c:1457
SCIProwGetRank
int SCIProwGetRank(SCIP_ROW *row)
Definition lp.c:17410
SCIProwChgRank
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition lp.c:17563
SCIProwGetConstant
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition lp.c:17287
SCIPgetRowNumIntCols
int SCIPgetRowNumIntCols(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1890
SCIProwGetVals
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition lp.c:17277
SCIPgetRowSolActivity
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition scip_lp.c:2148
SCIPincludeSepaBasic
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition scip_sepa.c:115
SCIPsetSepaFree
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:173
SCIPsepaGetName
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition sepa.c:743
SCIPsepaGetNCallsAtNode
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition sepa.c:880
SCIPsetSepaExit
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:205
SCIPsetSepaInit
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:189
SCIPsepaGetData
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition sepa.c:633
SCIPsepaSetData
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition sepa.c:643
SCIPsetSepaCopy
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:157
SCIPsepaGetNCalls
SCIP_Longint SCIPsepaGetNCalls(SCIP_SEPA *sepa)
Definition sepa.c:860
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2165
SCIPsetSolVal
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1073
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1213
SCIPgetMaxDepth
int SCIPgetMaxDepth(SCIP *scip)
Definition scip_solvingstats.c:1201
SCIPgetNRuns
int SCIPgetNRuns(SCIP *scip)
Definition scip_solvingstats.c:130
SCIPgetNRootFirstLPIterations
SCIP_Longint SCIPgetNRootFirstLPIterations(SCIP *scip)
Definition scip_solvingstats.c:509
SCIPgetNNodeInitLPIterations
SCIP_Longint SCIPgetNNodeInitLPIterations(SCIP *scip)
Definition scip_solvingstats.c:821
SCIPgetNLPIterations
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition scip_solvingstats.c:446
SCIPgetSolvingTime
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition scip_timing.c:378
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition scip_numerics.c:510
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:497
SCIPfeasFrac
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:941
SCIPisPositive
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:570
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:471
SCIPisFeasZero
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:845
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:521
SCIPisFeasNegative
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:869
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:484
SCIPisNegative
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:582
SCIPceil
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:643
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:445
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:558
SCIPepsilon
SCIP_Real SCIPepsilon(SCIP *scip)
Definition scip_numerics.c:137
SCIPsumepsilon
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition scip_numerics.c:151
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:458
SCIPisFeasPositive
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:857
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17602
SCIPrandomGetReal
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition misc.c:10131
SCIPincludeSepaLagromory
SCIP_RETCODE SCIPincludeSepaLagromory(SCIP *scip)
Definition sepa_lagromory.c:3216
SCIPsortDownRealInt
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10878
result
* result
Definition heur_actconsdiving.c:293
SCIP_OKAY
return SCIP_OKAY
Definition heur_actconsdiving.c:235
SCIPfreeSol
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPfreeRandom
SCIPfreeRandom(scip, &heurdata->randnumgen)
lperror
SCIP_Bool lperror
Definition heur_intdiving.c:205
ncalls
SCIP_Longint ncalls
Definition heur_intdiving.c:208
c
int c
Definition heur_intdiving.c:219
maxdepth
int maxdepth
Definition heur_intdiving.c:215
depth
int depth
Definition heur_intdiving.c:214
cutoff
SCIP_Bool cutoff
Definition heur_intdiving.c:206
objval
SCIP_Real objval
Definition heur_intdiving.c:204
SCIPcreateRandom
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
sol
static SCIP_SOL * sol
Definition heur_intshifting.c:693
assert
assert(minobj< SCIPgetCutoffbound(scip))
var
SCIP_VAR * var
Definition heur_objpscostdiving.c:264
SCIPendDive
SCIPendDive(scip))
frac
SCIP_Real frac
Definition heur_objpscostdiving.c:269
alpha
SCIP_Real alpha
Definition heur_rootsoldiving.c:197
i
int i
Definition heur_rootsoldiving.c:212
heur_trysol.h
primal heuristic that tries a given solution
BMSclearMemory
#define BMSclearMemory(ptr)
Definition memory.h:129
BMS_BLKMEM
struct BMS_BlkMem BMS_BLKMEM
Definition memory.h:437
SCIPblkmem
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
SEPA_PRIORITY
#define SEPA_PRIORITY
Definition sepa_aggregation.c:78
SEPA_DELAY
#define SEPA_DELAY
Definition sepa_aggregation.c:82
DEFAULT_DYNAMICCUTS
#define DEFAULT_DYNAMICCUTS
Definition sepa_aggregation.c:112
SEPA_DESC
#define SEPA_DESC
Definition sepa_aggregation.c:77
MAKECONTINTEGRAL
#define MAKECONTINTEGRAL
Definition sepa_aggregation.c:119
SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP
Definition sepa_aggregation.c:81
SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST
Definition sepa_aggregation.c:80
SEPA_FREQ
#define SEPA_FREQ
Definition sepa_aggregation.c:79
SEPA_NAME
#define SEPA_NAME
Definition sepa_aggregation.c:76
FIXINTEGRALRHS
#define FIXINTEGRALRHS
Definition sepa_cgmip.c:172
MAXAGGRLEN
#define MAXAGGRLEN(nvars)
Definition sepa_cgmip.c:178
sepadata
sepadata
Definition sepa_disjunctive.c:467
DEFAULT_MAKEINTEGRAL
#define DEFAULT_MAKEINTEGRAL
Definition sepa_gomory.c:101
DEFAULT_DELAYEDCUTS
#define DEFAULT_DELAYEDCUTS
Definition sepa_gomory.c:104
DEFAULT_SIDETYPEBASIS
#define DEFAULT_SIDETYPEBASIS
Definition sepa_gomory.c:105
DEFAULT_AWAY
#define DEFAULT_AWAY
Definition sepa_gomory.c:100
DEFAULT_FORCECUTS
#define DEFAULT_FORCECUTS
Definition sepa_gomory.c:102
DEFAULT_SEPARATEROWS
#define DEFAULT_SEPARATEROWS
Definition sepa_gomory.c:103
DEFAULT_MAXLAGRANGIANVALSFORAVG
#define DEFAULT_MAXLAGRANGIANVALSFORAVG
Definition sepa_lagromory.c:202
DEFAULT_DELTASLAB1UB
#define DEFAULT_DELTASLAB1UB
Definition sepa_lagromory.c:194
DEFAULT_UBPARAMNEGFACTOR
#define DEFAULT_UBPARAMNEGFACTOR
Definition sepa_lagromory.c:200
DEFAULT_VARCONSRATIOTHRESHOLD
#define DEFAULT_VARCONSRATIOTHRESHOLD
Definition sepa_lagromory.c:161
DEFAULT_DUALDEGENERACYRATETHRESHOLD
#define DEFAULT_DUALDEGENERACYRATETHRESHOLD
Definition sepa_lagromory.c:160
DEFAULT_MUPARAMINIT
#define DEFAULT_MUPARAMINIT
Definition sepa_lagromory.c:183
sepadataCreate
static SCIP_RETCODE sepadataCreate(SCIP *scip, SCIP_SEPADATA **sepadata)
Definition sepa_lagromory.c:3010
DEFAULT_MUPARAMUB
#define DEFAULT_MUPARAMUB
Definition sepa_lagromory.c:185
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)
Definition sepa_lagromory.c:683
DEFAULT_CONST
#define DEFAULT_CONST
Definition sepa_lagromory.c:224
DEFAULT_ALLOWLOCAL
#define DEFAULT_ALLOWLOCAL
Definition sepa_lagromory.c:155
deleteLPWithSoftCuts
static SCIP_RETCODE deleteLPWithSoftCuts(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition sepa_lagromory.c:431
DEFAULT_UBPARAMPOSFACTOR
#define DEFAULT_UBPARAMPOSFACTOR
Definition sepa_lagromory.c:198
linfBallProjection
static void linfBallProjection(SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)
Definition sepa_lagromory.c:1165
DEFAULT_MAXSUBGRADIENTITERS
#define DEFAULT_MAXSUBGRADIENTITERS
Definition sepa_lagromory.c:179
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)
Definition sepa_lagromory.c:1996
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)
Definition sepa_lagromory.c:1440
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)
Definition sepa_lagromory.c:1773
DEFAULT_MUPARAMLB
#define DEFAULT_MUPARAMLB
Definition sepa_lagromory.c:184
DEFAULT_RADIUSMAX
#define DEFAULT_RADIUSMAX
Definition sepa_lagromory.c:222
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)
Definition sepa_lagromory.c:1284
DEFAULT_PERLPMAXCUTSROOT
#define DEFAULT_PERLPMAXCUTSROOT
Definition sepa_lagromory.c:164
DEFAULT_PROJECTIONTYPE
#define DEFAULT_PROJECTIONTYPE
Definition sepa_lagromory.c:216
DEFAULT_CUTADDFREQ
#define DEFAULT_CUTADDFREQ
Definition sepa_lagromory.c:209
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)
Definition sepa_lagromory.c:2643
DEFAULT_MUSLAB2FACTOR
#define DEFAULT_MUSLAB2FACTOR
Definition sepa_lagromory.c:190
DEFAULT_RADIUSINIT
#define DEFAULT_RADIUSINIT
Definition sepa_lagromory.c:221
DEFAULT_TOTALCUTSFACTOR
#define DEFAULT_TOTALCUTSFACTOR
Definition sepa_lagromory.c:177
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)
Definition sepa_lagromory.c:2529
DEFAULT_PERROUNDMAXLPITERS
#define DEFAULT_PERROUNDMAXLPITERS
Definition sepa_lagromory.c:172
DEFAULT_PERROUNDCUTSFACTOR
#define DEFAULT_PERROUNDCUTSFACTOR
Definition sepa_lagromory.c:175
DEFAULT_MAXMAINITERS
#define DEFAULT_MAXMAINITERS
Definition sepa_lagromory.c:178
DEFAULT_PERROUNDCUTSFACTORROOT
#define DEFAULT_PERROUNDCUTSFACTORROOT
Definition sepa_lagromory.c:173
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)
Definition sepa_lagromory.c:807
l1BallProjection
static SCIP_RETCODE l1BallProjection(SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)
Definition sepa_lagromory.c:994
DEFAULT_OPTIMALFACEPRIORITY
#define DEFAULT_OPTIMALFACEPRIORITY
Definition sepa_lagromory.c:211
DEFAULT_SORTCUTOFFSOL
#define DEFAULT_SORTCUTOFFSOL
Definition sepa_lagromory.c:150
separateCuts
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_Real ubparam, int depth, SCIP_Bool allowlocal, SCIP_RESULT *result)
Definition sepa_lagromory.c:2691
DEFAULT_MUSLAB1FACTOR
#define DEFAULT_MUSLAB1FACTOR
Definition sepa_lagromory.c:188
DEFAULT_PERROUNDLPITERLIMITFACTOR
#define DEFAULT_PERROUNDLPITERLIMITFACTOR
Definition sepa_lagromory.c:166
DEFAULT_CUTSFILTERFACTOR
#define DEFAULT_CUTSFILTERFACTOR
Definition sepa_lagromory.c:210
sepadataFree
static SCIP_RETCODE sepadataFree(SCIP *scip, SCIP_SEPADATA **sepadata)
Definition sepa_lagromory.c:647
createLPWithSoftCuts
static SCIP_RETCODE createLPWithSoftCuts(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition sepa_lagromory.c:350
updateObjectiveVector
static SCIP_RETCODE updateObjectiveVector(SCIP *scip, SCIP_Real *dualvector, SCIP_ROW **cuts, int ncuts, SCIP_Real *origobjcoefs, SCIP_Bool *objvecsdiffer)
Definition sepa_lagromory.c:2186
addGMICutsAsSoftConss
static SCIP_RETCODE addGMICutsAsSoftConss(SCIP_Real *dualvector, int ngeneratedcuts, int *naddedcuts, int *nnewaddedsoftcuts)
Definition sepa_lagromory.c:2271
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)
Definition sepa_lagromory.c:2566
solveLPWithHardCuts
static SCIP_RETCODE solveLPWithHardCuts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Bool *solfound, SCIP_SOL *sol, SCIP_Real *solvals)
Definition sepa_lagromory.c:1577
DEFAULT_PERLPITERFACTOR
#define DEFAULT_PERLPITERFACTOR
Definition sepa_lagromory.c:206
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)
Definition sepa_lagromory.c:1393
createLPWithHardCuts
static SCIP_RETCODE createLPWithHardCuts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW **cuts, int ncuts)
Definition sepa_lagromory.c:448
DEFAULT_STABILITYCENTERTYPE
#define DEFAULT_STABILITYCENTERTYPE
Definition sepa_lagromory.c:219
DEFAULT_RADIUSMIN
#define DEFAULT_RADIUSMIN
Definition sepa_lagromory.c:223
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)
Definition sepa_lagromory.c:2295
DEFAULT_PERROOTLPITERFACTOR
#define DEFAULT_PERROOTLPITERFACTOR
Definition sepa_lagromory.c:204
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)
Definition sepa_lagromory.c:1641
DEFAULT_ROOTLPITERLIMITFACTOR
#define DEFAULT_ROOTLPITERLIMITFACTOR
Definition sepa_lagromory.c:168
DEFAULT_AGGREGATECUTS
#define DEFAULT_AGGREGATECUTS
Definition sepa_lagromory.c:213
DEFAULT_MUBACKTRACKFACTOR
#define DEFAULT_MUBACKTRACKFACTOR
Definition sepa_lagromory.c:186
updateLagrangianValue
static void updateLagrangianValue(SCIP *scip, SCIP_Real objval, SCIP_Real *dualvector, SCIP_ROW **cuts, int ncuts, SCIP_Real *lagrangianval)
Definition sepa_lagromory.c:878
DEFAULT_MINRESTART
#define DEFAULT_MINRESTART
Definition sepa_lagromory.c:162
DEFAULT_CUTGENFREQ
#define DEFAULT_CUTGENFREQ
Definition sepa_lagromory.c:208
updateStepLength
static void updateStepLength(SCIP *scip, SCIP_Real muparam, SCIP_Real ubparam, SCIP_Real lagrangianval, SCIP_Real *subgradient, int ncuts, SCIP_Real *steplength)
Definition sepa_lagromory.c:903
DEFAULT_RADIUSUPDATEWEIGHT
#define DEFAULT_RADIUSUPDATEWEIGHT
Definition sepa_lagromory.c:225
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)
Definition sepa_lagromory.c:925
l2BallProjection
static void l2BallProjection(SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)
Definition sepa_lagromory.c:1134
DEFAULT_DELTASLAB2UB
#define DEFAULT_DELTASLAB2UB
Definition sepa_lagromory.c:196
DEFAULT_MUPARAMCONST
#define DEFAULT_MUPARAMCONST
Definition sepa_lagromory.c:182
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)
Definition sepa_lagromory.c:1224
DEFAULT_TOTALLPITERLIMITFACTOR
#define DEFAULT_TOTALLPITERLIMITFACTOR
Definition sepa_lagromory.c:170
DEFAULT_PERLPMAXCUTS
#define DEFAULT_PERLPMAXCUTS
Definition sepa_lagromory.c:165
weightedDualVector
static void weightedDualVector(SCIP_SEPADATA *sepadata, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real *stabilitycenter, int stabilitycenterlen, int nbestdualupdates, int totaliternum)
Definition sepa_lagromory.c:1191
DEFAULT_MUSLAB3FACTOR
#define DEFAULT_MUSLAB3FACTOR
Definition sepa_lagromory.c:192
DEFAULT_MAXCONSECITERSFORMUUPDATE
#define DEFAULT_MAXCONSECITERSFORMUUPDATE
Definition sepa_lagromory.c:203
sepa_lagromory.h
lagromory separator
SCIP_AGGRROW
struct SCIP_AggrRow SCIP_AGGRROW
Definition type_cuts.h:37
SCIP_HEUR
struct SCIP_Heur SCIP_HEUR
Definition type_heur.h:76
SCIP_ROW
struct SCIP_Row SCIP_ROW
Definition type_lp.h:104
SCIP_LPSOLSTAT
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition type_lp.h:51
SCIP_COL
struct SCIP_Col SCIP_COL
Definition type_lp.h:98
SCIP_LPSOLSTAT_OPTIMAL
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
SCIP_LPISTATE
struct SCIP_LPiState SCIP_LPISTATE
Definition type_lpi.h:107
SCIP_LPI
struct SCIP_LPi SCIP_LPI
Definition type_lpi.h:106
SCIP_LPPAR_LPTILIM
@ SCIP_LPPAR_LPTILIM
Definition type_lpi.h:61
SCIP_OBJSEN_MINIMIZE
@ SCIP_OBJSEN_MINIMIZE
Definition type_lpi.h:43
SCIP_RANDNUMGEN
struct SCIP_RandNumGen SCIP_RANDNUMGEN
Definition type_misc.h:126
SCIP_DIDNOTRUN
@ SCIP_DIDNOTRUN
Definition type_result.h:42
SCIP_CUTOFF
@ SCIP_CUTOFF
Definition type_result.h:48
SCIP_DIDNOTFIND
@ SCIP_DIDNOTFIND
Definition type_result.h:44
SCIP_SEPARATED
@ SCIP_SEPARATED
Definition type_result.h:49
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition type_retcode.h:63
SCIP
struct Scip SCIP
Definition type_scip.h:39
SCIP_SEPADATA
struct SCIP_SepaData SCIP_SEPADATA
Definition type_sepa.h:52
SCIP_DECL_SEPAEXECLP
#define SCIP_DECL_SEPAEXECLP(x)
Definition type_sepa.h:136
SCIP_DECL_SEPAFREE
#define SCIP_DECL_SEPAFREE(x)
Definition type_sepa.h:69
SCIP_DECL_SEPAEXIT
#define SCIP_DECL_SEPAEXIT(x)
Definition type_sepa.h:85
SCIP_SEPA
struct SCIP_Sepa SCIP_SEPA
Definition type_sepa.h:51
SCIP_DECL_SEPACOPY
#define SCIP_DECL_SEPACOPY(x)
Definition type_sepa.h:61
SCIP_DECL_SEPAINIT
#define SCIP_DECL_SEPAINIT(x)
Definition type_sepa.h:77
SCIP_SOL
struct SCIP_Sol SCIP_SOL
Definition type_sol.h:57
SCIP_VAR
struct SCIP_Var SCIP_VAR
Definition type_var.h:119
SCIP_VARTYPE_CONTINUOUS
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71