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