Scippy

SCIP

Solving Constraint Integer Programs

sepa_cgmip.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24/* #define SCIP_WRITEPROB */
25/* #define SCIP_OUTPUT */
26/**@file sepa_cgmip.c
27 * @ingroup DEFPLUGINS_SEPA
28 * @brief Chvatal-Gomory cuts computed via a sub-MIP
29 * @author Marc Pfetsch
30 *
31 * Separate Chvátal-Gomory cuts using a sub-MIP. The approach is based on the following papers.
32 *
33 * M. Fischetti and A. Lodi@n
34 * Optimizing over the first Chvátal closure,@n
35 * in: M. Jünger and V. Kaibel (eds.) Integer Programming and Combinatorial Optimization IPCO 2005,@n
36 * LNCS 3509, pp. 12-22. Springer, Berlin Heidelberg New York (2005)
37 *
38 * M. Fischetti and A. Lodi@n
39 * Optimizing over the first Chvátal closure,@n
40 * Mathematical Programming 110, 3-20 (2007)
41 *
42 * P. Bonami, G. Cornuéjols, S. Dash, M. Fischetti, and A. Lodi@n
43 * Projected Chvátal-Gomory cuts for mixed integer linear programs,@n
44 * Mathematical Programming 113, No. 2 (2008)
45 *
46 *
47 * There are several possibilities to generate the final cut:
48 *
49 * - The CMIR-routines of SCIP can be used (if @p usecmir is true). One can determine which bound is
50 * used in the rounding operation (if @p cmirownbounds is true) or let SCIP choose the best. This
51 * version is generally numerically the most stable.
52 * - If @p usestrongcg is true, we try to generate Strong-CG cuts (as done in sepa_strongcg.c).
53 * - One can directly generate the CG-cut as computed (if @p usecmir and @p usestrongcg are
54 * false). The cut is not taken from the solution of the MIP, but is recomputed, and some care (but
55 * not as much as in the first version) has been taken to create a valid cut.
56 *
57 * The computation time of the separation MIP is limited as follows:
58 * - There is a node limit (parameters @a minnodelimit and @a maxnodelimit).
59 * - There is a time limit (parameter @a timelimit).
60 * - If paramter @a earlyterm is true, the separation is run until the first cut that is violated is
61 * found. (Note that these cuts are not necessarily added to the LP, because here also the norm of
62 * the cuts are taken into account - which cannot easily be included into the separation subscip.)
63 * Then the solution process is continued for a certain number of nodes.
64 *
65 * @todo Check whether one can weaken the conditions on the continuous variables.
66 * @todo Use pointers to originating separators to sort out cuts that should not be used.
67 *
68 * @warning This separator should be used carefully - it may require a long separation time.
69 */
70
71/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
72
73#include "blockmemshell/memory.h"
74#include "scip/cons_linear.h"
75#include "scip/cuts.h"
76#include "scip/pub_cons.h"
77#include "scip/pub_lp.h"
78#include "scip/pub_message.h"
79#include "scip/pub_misc.h"
80#include "scip/pub_sepa.h"
81#include "scip/pub_var.h"
82#include "scip/scip_branch.h"
83#include "scip/scip_cons.h"
84#include "scip/scip_copy.h"
85#include "scip/scip_cut.h"
86#include "scip/scip_general.h"
87#include "scip/scip_lp.h"
88#include "scip/scip_mem.h"
89#include "scip/scip_message.h"
90#include "scip/scip_numerics.h"
91#include "scip/scip_param.h"
92#include "scip/scip_prob.h"
93#include "scip/scip_randnumgen.h"
94#include "scip/scip_sepa.h"
95#include "scip/scip_sol.h"
96#include "scip/scip_solve.h"
97#include "scip/scip_solvingstats.h"
98#include "scip/scip_timing.h"
99#include "scip/scip_tree.h"
100#include "scip/scip_var.h"
101#include "scip/scipdefplugins.h"
102#include "scip/sepa_cgmip.h"
103#include <string.h>
104
105
106#define SEPA_NAME "cgmip"
107#define SEPA_DESC "Chvatal-Gomory cuts via MIPs separator"
108#define SEPA_PRIORITY -1000
109#define SEPA_FREQ -1
110#define SEPA_MAXBOUNDDIST 0.0
111#define SEPA_USESSUBSCIP TRUE /**< does the separator use a secondary SCIP instance? */
112#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
113
114#define DEFAULT_MAXROUNDS 5 /**< maximal number of separation rounds per node (-1: unlimited) */
115#define DEFAULT_MAXROUNDSROOT 50 /**< maximal number of separation rounds in the root node (-1: unlimited) */
116#define DEFAULT_MAXDEPTH -1 /**< maximal depth at which the separator is applied */
117#define DEFAULT_DECISIONTREE FALSE /**< Use decision tree to turn separation on/off? */
118#define DEFAULT_TIMELIMIT 1e20 /**< time limit for sub-MIP (set to infinity in order to be deterministic) */
119#define DEFAULT_MEMORYLIMIT 1e20 /**< memory limit for sub-MIP */
120#define DEFAULT_CUTCOEFBND 1000.0 /**< bounds on the values of the coefficients in the CG-cut */
121#define DEFAULT_MINNODELIMIT 500LL /**< minimum number of nodes considered for sub-MIP (-1: unlimited) */
122#define DEFAULT_MAXNODELIMIT 5000LL /**< maximum number of nodes considered for sub-MIP (-1: unlimited) */
123#define DEFAULT_ONLYACTIVEROWS FALSE /**< Use only active rows to generate cuts? */
124#define DEFAULT_MAXROWAGE -1 /**< maximal age of rows to consider if onlyactiverows is false */
125#define DEFAULT_ONLYRANKONE FALSE /**< Separate rank 1 inequalities w.r.t. CG-MIP separator? */
126#define DEFAULT_ONLYINTVARS FALSE /**< Generate cuts for problems with only integer variables? */
127#define DEFAULT_CONTCONVERT FALSE /**< Convert some integral variables to be continuous to reduce the size of the sub-MIP? */
128#define DEFAULT_CONTCONVFRAC 0.1 /**< fraction of integral variables converted to be continuous (if contconvert) */
129#define DEFAULT_CONTCONVMIN 100 /**< minimum number of integral variables before some are converted to be continuous */
130#define DEFAULT_INTCONVERT FALSE /**< Convert some integral variables attaining fractional values to have integral value? */
131#define DEFAULT_INTCONVFRAC 0.1 /**< fraction of fractional integral variables converted to have integral value (if intconvert) */
132#define DEFAULT_INTCONVMIN 100 /**< minimum number of integral variables before some are converted to have integral value */
133#define DEFAULT_SKIPMULTBOUNDS TRUE /**< Skip the upper bounds on the multipliers in the sub-MIP? */
134#define DEFAULT_OBJLONE FALSE /**< Should the objective of the sub-MIP only minimize the l1-norm of the multipliers? */
135#define DEFAULT_OBJWEIGHT 1e-03 /**< objective weight for artificial variables */
136#define DEFAULT_OBJWEIGHTSIZE TRUE /**< Weight each row by its size? */
137#define DEFAULT_DYNAMICCUTS TRUE /**< Should generated cuts be removed from the LP if they are no longer tight? */
138#define DEFAULT_USECMIR TRUE /**< Use CMIR-generator (otherwise add cut directly)? */
139#define DEFAULT_USESTRONGCG FALSE /**< Use strong CG-function to strengthen cut? */
140#define DEFAULT_CMIROWNBOUNDS FALSE /**< Tell CMIR-generator which bounds to used in rounding? */
141#define DEFAULT_USECUTPOOL TRUE /**< Use cutpool to store CG-cuts even if the are not efficient? */
142#define DEFAULT_PRIMALSEPARATION TRUE /**< Only separate cuts that are tight for the best feasible solution? */
143#define DEFAULT_EARLYTERM TRUE /**< Terminate separation if a violated (but possibly sub-optimal) cut has been found? */
144#define DEFAULT_ADDVIOLATIONCONS FALSE /**< Add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?*/
145#define DEFAULT_ADDVIOLCONSHDLR FALSE /**< Add constraint handler to filter out violated cuts? */
146#define DEFAULT_CONSHDLRUSENORM TRUE /**< Should the violation constraint handler use the norm of a cut to check for feasibility? */
147#define DEFAULT_USEOBJUB FALSE /**< Use upper bound on objective function (via primal solution)? */
148#define DEFAULT_USEOBJLB FALSE /**< Use lower bound on objective function (via lower bound)? */
149#define DEFAULT_SUBSCIPFAST TRUE /**< Should the settings for the sub-MIP be optimized for speed? */
150#define DEFAULT_OUTPUT FALSE /**< Should information about the sub-MIP and cuts be displayed? */
151#define DEFAULT_RANDSEED 101 /**< start random seed for random number generation */
152#define DEFAULT_GENPRIMALSOLS FALSE /**< Try to generate primal solutions from Gomory cuts? */
153
154
155#define NROWSTOOSMALL 5 /**< only separate if the number of rows is larger than this number */
156#define NCOLSTOOSMALL 5 /**< only separate if the number of columns is larger than this number */
157
158#define EPSILONVALUE 1e-03 /**< epsilon value needed to model strict-inequalities */
159#define BETAEPSILONVALUE 1e-02 /**< epsilon value for fracbeta - is larger than EPSILONVALUE for numerical stability */
160#define STALLNODELIMIT 1000LL /**< number of stalling nodes if earlyterm is true */
161#define CONSHDLRFULLNORM FALSE /**< compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true) */
162#define MINEFFICACY 0.05 /**< minimum efficacy of a cut - compare set.c */
163#define MAXNSOLS 1000 /**< maximal number of solutions stored in sub-SCIP */
164#define OBJWEIGHTRANGE 0.01 /**< maximal range of scaling of objective w.r.t. size of rows */
165
166/* parameters used for CMIR-generation (taken from sepa_gomory) */
167#define BOUNDSWITCH 0.9999
168#define VARTYPEUSEVBDS 2 /**< We allow variable bound substitution for variables with continuous vartype only.
169 * See SCIPcalcMIR() for more information. */
170#define POSTPROCESS TRUE
171#define MINFRAC 0.0009 /**< to allow a deviation of the same size as EPSILONVALUE */
172#define MAXFRAC 0.9991 /**< to allow a deviation of the same size as EPSILONVALUE */
173#define FIXINTEGRALRHS FALSE
174#define MAKECONTINTEGRAL FALSE
175#define MAXWEIGHTRANGE 1e+05 /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
176#define AWAY 0.005 /**< minimal fractionality of a basic variable in order to try GMI cut */
177#define SEPARATEROWS TRUE /**< Separate rows with integral slack? */
178
179#define MAXAGGRLEN(nvars) nvars /**< currently very large to allow any generation; an alternative would be (0.1*(nvars)+1000) */
180
181/** separator data */
182struct SCIP_SepaData
183{
184 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
185 int maxrounds; /**< maximal number of separation rounds per node (-1: unlimited) */
186 int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: unlimited) */
187 int maxdepth; /**< maximal depth at which the separator is applied */
188 SCIP_Bool decisiontree; /**< Use decision tree to turn separation on/off? */
189 SCIP_Real timelimit; /**< time limit for subscip */
190 SCIP_Real memorylimit; /**< memory limit for subscip */
191 SCIP_Longint minnodelimit; /**< minimum number of nodes considered for sub-MIP (-1: unlimited) */
192 SCIP_Longint maxnodelimit; /**< maximum number of nodes considered for sub-MIP (-1: unlimited) */
193 SCIP_Real cutcoefbnd; /**< bounds on the values of the coefficients in the CG-cut */
194 SCIP_Bool onlyactiverows; /**< Use only active rows to generate cuts? */
195 int maxrowage; /**< maximal age of rows to consider if onlyactiverows is false */
196 SCIP_Bool onlyrankone; /**< Separate only rank 1 inequalities w.r.t. CG-MIP separator? */
197 SCIP_Bool onlyintvars; /**< Generate cuts for problems with only integer variables? */
198 SCIP_Bool allowlocal; /**< Allow local cuts? */
199 SCIP_Bool contconvert; /**< Convert some integral variables to be continuous to reduce the size of the sub-MIP? */
200 SCIP_Real contconvfrac; /**< fraction of integral variables converted to be continuous (if contconvert) */
201 int contconvmin; /**< minimum number of integral variables before some are converted to be continuous */
202 SCIP_Bool intconvert; /**< Convert some integral variables attaining fractional values to have integral value? */
203 SCIP_Real intconvfrac; /**< fraction of frac. integral variables converted to have integral value (if intconvert) */
204 int intconvmin; /**< minimum number of integral variables before some are converted to have integral value */
205 SCIP_Bool skipmultbounds; /**< Skip the upper bounds on the multipliers in the sub-MIP? */
206 SCIP_Bool objlone; /**< Should the objective of the sub-MIP only minimize the l1-norm of the multipliers? */
207 SCIP_Real objweight; /**< objective weight for artificial variables */
208 SCIP_Bool objweightsize; /**< Weight each row by its size? */
209 SCIP_Bool dynamiccuts; /**< Should generated cuts be removed from the LP if they are no longer tight? */
210 SCIP_Bool usecmir; /**< Use CMIR-generator (otherwise add cut directly)? */
211 SCIP_Bool usestrongcg; /**< Use strong CG-function to strengthen cut? */
212 SCIP_Bool cmirownbounds; /**< Tell CMIR-generator which bounds to used in rounding? */
213 SCIP_Bool usecutpool; /**< Use cutpool to store CG-cuts even if the are not efficient? */
214 SCIP_Bool primalseparation; /**< Only separate cuts that are tight for the best feasible solution? */
215 SCIP_Bool earlyterm; /**< Terminate separation if a violated (but possibly sub-optimal) cut has been found? */
216 SCIP_Bool addviolationcons; /**< Add constraint to subscip that only allows violated cuts? */
217 SCIP_Bool addviolconshdlr; /**< Add constraint handler to filter out violated cuts? */
218 SCIP_Bool conshdlrusenorm; /**< Should the violation constraint handler use the cut-norm to check for feasibility? */
219 SCIP_Bool useobjub; /**< Use upper bound on objective function (via primal solution)? */
220 SCIP_Bool useobjlb; /**< Use lower bound on objective function (via lower bound)? */
221 SCIP_Bool subscipfast; /**< Should the settings for the sub-MIP be optimized for speed? */
222 SCIP_Bool output; /**< Should information about the sub-MIP and cuts be displayed? */
223 SCIP_Bool genprimalsols; /**< Try to generate primal solutions from Gomory cuts? */
224};
225
226
227/** what happens for columns in the LP */
228enum CGMIP_ColType
229{
230 colPresent = 0, /**< column is present in the separating MIP */
231 colContinuous = 1, /**< column corresponds to a continuous variable */
232 colConverted = 2, /**< column is converted to be continuous */
233 colAtUb = 3, /**< variable corresponding to column was at it's upper bound and was complemented */
234 colAtLb = 4 /**< variable corresponding to column was at it's lower bound (possibly complemented) */
235};
236typedef enum CGMIP_ColType CGMIP_COLTYPE;
237
238
239/** data for the sub-MIP */
240struct CGMIP_MIPData
241{
242 SCIP* subscip; /**< pointer to (sub)SCIP data structure containing the auxiliary IP */
243 unsigned int m; /**< number of constraints of subscip */
244 unsigned int n; /**< number of variables of subscip */
245 unsigned int nrows; /**< number of rows of original LP */
246 unsigned int ncols; /**< number of columns of original LP */
247 unsigned int ntotalrows; /**< number of total rows used (possibly including objective rows) */
248
249 SCIP_VAR** alpha; /**< cut coefficient variable (NULL if not in separating MIP) */
250 SCIP_VAR* beta; /**< rhs of cut */
251 SCIP_VAR** fracalpha; /**< fractional part of lhs of cut (NULL if not present) */
252 SCIP_VAR* fracbeta; /**< fractional part of rhs of cut */
253 CGMIP_COLTYPE* coltype; /**< type for the columns */
254 SCIP_Bool* iscomplemented; /**< whether the variable was complemented */
255 SCIP_Bool* isshifted; /**< whether the variable was shifted to have 0 lower bound */
256
257 SCIP_VAR** ylhs; /**< auxiliary row variables for lhs (NULL if not present) */
258 SCIP_VAR** yrhs; /**< auxiliary row variables for rhs (NULL if not present) */
259
260 SCIP_VAR** z; /**< auxiliary variables for upper bounds (NULL if not present) */
261
262 SCIP_Real* lhs; /**< transformed left hand sides */
263 SCIP_Real* rhs; /**< transformed left hand sides */
264
265 char normtype; /**< type of norm to use for efficacy norm calculation */
266
267 /* additional redundant data */
268 SCIP_Bool conshdlrusenorm; /**< copy from sepadata */
269 SCIP_Bool conshdlrfullnorm; /**< compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true) */
270 SCIP* scip; /**< original SCIP */
271 SCIP_SEPA* sepa; /**< CG-cut separator */
272 SCIP_SEPADATA* sepadata; /**< CG-cut separator data */
273};
274typedef struct CGMIP_MIPData CGMIP_MIPDATA;
275
276
277/*
278 * constraint handler to filter out violated cuts
279 */
280
281/* constraint handler properties */
282#define CONSHDLR_NAME "violatedCuts"
283#define CONSHDLR_DESC "only allow solutions corresponding to violated cuts"
284
285/** constraint handler data */
286struct SCIP_ConshdlrData
287{
288 CGMIP_MIPDATA* mipdata; /**< data of separating sub-MIP */
289};
290
291/* temporary forward declaration */
292static
293SCIP_RETCODE computeCut(
294 SCIP* scip, /**< original scip */
295 SCIP_SEPA* sepa, /**< separator */
296 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
297 SCIP_SEPADATA* sepadata, /**< separator data */
298 SCIP_SOL* sol, /**< current solution for sub-MIP */
299 SCIP_Bool usefrac, /**< use fractional value of multipliers */
300 SCIP_Real* cutcoefs, /**< coefficients of the cut */
301 SCIP_Real* cutrhs, /**< rhs of the cut */
302 SCIP_Bool* localrowsused, /**< pointer to store whether local rows were used in summation */
303 SCIP_Bool* localboundsused, /**< pointer to store whether local bounds were used in summation */
304 int * cutrank, /**< pointer to store the cut rank */
305 SCIP_Bool* success /**< whether we produced a valid cut */
306 );
307
308/** check whether cut corresponding to solution is violated */
309static
310SCIP_RETCODE solCutIsViolated(
311 SCIP* scip, /**< SCIP data structure */
312 CGMIP_MIPDATA* mipdata, /**< data of separating sub-MIP */
313 SCIP_SOL* sol, /**< solution to be checked */
314 SCIP_Bool* violated /**< pointer to store if the cut is violated */
315 )
316{
317 SCIP_Real cutsqrnorm = 0.0;
318 SCIP* subscip;
319 SCIP_Real act;
320 SCIP_Real norm;
321 SCIP_Real val;
322 SCIP_VAR* var;
323 SCIP_Real rhs;
324 unsigned int j;
325 int len = 0;
326
327 assert( mipdata != NULL );
328 subscip = mipdata->subscip;
329 assert( subscip != NULL );
330 assert( violated != NULL );
331
332 /* initialize activity and norm */
333 act = 0.0;
334 norm = 1.0;
335 *violated = FALSE;
336
337 /* compute activity and norm */
338 if ( mipdata->conshdlrusenorm )
339 {
340 /* check whether we should compute the full cut and then compute the norm */
341 if ( mipdata->conshdlrfullnorm )
342 {
343 SCIP_Real* cutcoefs;
344 SCIP_Bool localrowsused;
345 SCIP_Bool localboundsused;
346 SCIP_Bool success;
347 SCIP_VAR** vars;
348 int cutrank = 0;
349 int nvars;
350
351 /* get data */
352 SCIP_CALL( SCIPgetVarsData(mipdata->scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
353 assert(nvars >= 0);
354 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
355
356 /* compute coefficients */
357 SCIP_CALL( computeCut(mipdata->scip, mipdata->sepa, mipdata, mipdata->sepadata, sol, TRUE, cutcoefs, &rhs, &localrowsused, &localboundsused, &cutrank, &success) );
358
359 /* try again if cut was not valid */
360 if ( ! success )
361 {
362 SCIP_CALL( computeCut(mipdata->scip, mipdata->sepa, mipdata, mipdata->sepadata, sol, FALSE,
363 cutcoefs, &rhs, &localrowsused, &localboundsused, &cutrank, &success) );
364
365 if ( ! success )
366 return SCIP_OKAY;
367 }
368
369#ifdef SCIP_MORE_DEBUG
370 for (j = 0; j < (unsigned int) nvars; ++j)
371 {
372 if ( ! SCIPisZero(scip, cutcoefs[j]) )
373 SCIPinfoMessage(scip, NULL, "+ %f x%d", cutcoefs[j], j);
374 }
375 SCIPinfoMessage(scip, NULL, "\n");
376#endif
377
378 /* compute activity and Euclidean norm (todo: use arbitrary norm) */
379 cutsqrnorm = 0.0;
380 for (j = 0; j < (unsigned int) nvars; ++j)
381 {
382 if ( ! SCIPisZero(scip, cutcoefs[j]) )
383 {
384 act += cutcoefs[j] * SCIPvarGetLPSol(vars[j]);
385 cutsqrnorm += SQR(cutcoefs[j]);
386 }
387 }
388 norm = sqrt(cutsqrnorm);
389
390 SCIPfreeBufferArray(scip, &cutcoefs);
391 } /*lint !e438*/
392 else
393 {
394 switch ( mipdata->normtype )
395 {
396 case 'e':
397 cutsqrnorm = 0.0;
398 for (j = 0; j < mipdata->ncols; ++j)
399 {
400 var = mipdata->alpha[j];
401 if ( var == NULL )
402 continue;
403
404 val = SCIPgetSolVal(subscip, sol, var);
405 if ( !SCIPisZero(scip, val) )
406 {
407 act += val * SCIPvarGetObj(var);
408 cutsqrnorm += SQR(val);
409 }
410 }
411 norm = sqrt(cutsqrnorm);
412 break;
413 case 'm':
414 for (j = 0; j < mipdata->ncols; ++j)
415 {
416 var = mipdata->alpha[j];
417 if ( var == NULL )
418 continue;
419
420 val = SCIPgetSolVal(subscip, sol, var);
421 if ( !SCIPisZero(scip, val) )
422 {
423 act += val * SCIPvarGetObj(var);
424 if ( REALABS(val) > norm )
425 norm = REALABS(val);
426 }
427 }
428 break;
429 case 's':
430 for (j = 0; j < mipdata->ncols; ++j)
431 {
432 var = mipdata->alpha[j];
433 if ( var == NULL )
434 continue;
435
436 val = SCIPgetSolVal(subscip, sol, var);
437 if ( !SCIPisZero(scip, val) )
438 {
439 act += val * SCIPvarGetObj(var);
440 norm += REALABS(val);
441 }
442 }
443 break;
444 case 'd':
445 for (j = 0; j < mipdata->ncols; ++j)
446 {
447 var = mipdata->alpha[j];
448 if ( var == NULL )
449 continue;
450
451 val = SCIPgetSolVal(subscip, sol, var);
452 if ( !SCIPisZero(scip, val) )
453 {
454 act += val * SCIPvarGetObj(var);
455 ++len;
456 }
457 }
458 if ( len > 0 )
459 norm = 1.0;
460 break;
461 default:
462 SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", mipdata->normtype);
463 return SCIP_INVALIDDATA;
464 }
465 /* get rhs */
466 rhs = SCIPgetSolVal(subscip, sol, mipdata->beta);
467 }
468
469 /* if norm is 0, the cut is trivial */
470 if ( SCIPisZero(subscip, norm) )
471 return SCIP_OKAY;
472 }
473 else
474 {
475 for (j = 0; j < mipdata->ncols; ++j)
476 {
477 var = mipdata->alpha[j];
478 if ( var == NULL )
479 continue;
480
481 val = SCIPgetSolVal(subscip, sol, var);
482 if ( !SCIPisZero(subscip, val) )
483 act += SCIPvarGetObj(var) * val;
484 }
485
486 /* get rhs */
487 rhs = SCIPgetSolVal(subscip, sol, mipdata->beta);
488 }
489
490#ifdef SCIP_DEBUG
491 if ( SCIPisEfficacious(subscip, (act - rhs)/norm) )
492 {
493 SCIPdebugMsg(scip, "Violated cut from solution - act: %f, rhs: %f, norm: %f, eff.: %f\n", act, rhs, norm, (act-rhs)/norm);
494 }
495 else
496 {
497 SCIPdebugMsg(scip, "Rejected cut from solution - act: %f, rhs: %f, norm: %f, eff.: %f\n", act, rhs, norm, (act-rhs)/norm);
498 }
499#endif
500
501 *violated = SCIPisEfficacious(subscip, (act - rhs)/norm);
502
503 return SCIP_OKAY;
504}
505
506
507/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
508static
509SCIP_DECL_CONSFREE(consFreeViolatedCuts)
510{ /*lint --e{715}*/
511 SCIP_CONSHDLRDATA* conshdlrdata;
512
513 assert( scip != NULL );
514 assert( conshdlr != NULL );
515 conshdlrdata = SCIPconshdlrGetData(conshdlr);
516 assert( conshdlrdata != NULL );
517
518 SCIPfreeBlockMemory(scip, &conshdlrdata);
519
520 return SCIP_OKAY;
521}
522
523
524/** constraint enforcing method of constraint handler for LP solutions */
525static
526SCIP_DECL_CONSENFOLP(consEnfolpViolatedCuts)
527{ /*lint --e{715}*/
528 SCIP_CONSHDLRDATA* conshdlrdata;
529 SCIP_Bool violated;
530
531 assert( scip != NULL );
532 assert( conshdlr != NULL );
533 assert( result != NULL );
534
535 assert( SCIPgetNLPBranchCands(scip) == 0 );
536
537 conshdlrdata = SCIPconshdlrGetData(conshdlr);
538 assert( conshdlrdata != NULL );
539
540 SCIP_CALL( solCutIsViolated(scip, conshdlrdata->mipdata, NULL, &violated) );
541
542 if ( violated )
543 *result = SCIP_FEASIBLE;
544 else
545 *result = SCIP_CUTOFF; /* cutoff, since all integer variables are integer, but the solution is not feasible */
546
547 return SCIP_OKAY;
548}
549
550
551/** constraint enforcing method of constraint handler for pseudo solutions */
552static
553SCIP_DECL_CONSENFOPS(consEnfopsViolatedCuts)
554{ /*lint --e{715}*/
555 assert( result != NULL );
556
557 /* this function should better not be called, since we need an LP solution for the sub-MIP to
558 * make sense, because of the multiplier variables. We therefore return SCIP_FEASIBLE. */
559 *result = SCIP_FEASIBLE;
560
561 return SCIP_OKAY;
562}
563
564
565/** feasibility check method of constraint handler for integral solutions */
566static
567SCIP_DECL_CONSCHECK(consCheckViolatedCuts)
568{ /*lint --e{715}*/
569 SCIP_CONSHDLRDATA* conshdlrdata;
570 SCIP_Bool violated;
571
572 assert( scip != NULL );
573 assert( conshdlr != NULL );
574 assert( sol != NULL );
575 assert( result != NULL );
576
577 conshdlrdata = SCIPconshdlrGetData(conshdlr);
578 assert( conshdlrdata != NULL );
579
580 SCIP_CALL( solCutIsViolated(scip, conshdlrdata->mipdata, sol, &violated) );
581
582 if ( violated )
583 *result = SCIP_FEASIBLE;
584 else
585 *result = SCIP_INFEASIBLE;
586
587 return SCIP_OKAY;
588}
589
590
591/** variable rounding lock method of constraint handler */
592static
593SCIP_DECL_CONSLOCK(consLockViolatedCuts)
594{ /*lint --e{715}*/
595 /* do not lock variables */
596 return SCIP_OKAY;
597}
598
599
600/** creates the violated CG-cut constraint handler and includes it in SCIP */
601static
602SCIP_RETCODE SCIPincludeConshdlrViolatedCut(
603 SCIP* scip, /**< SCIP data structure */
604 CGMIP_MIPDATA* mipdata /**< data of separating sub-MIP */
605 )
606{
607 SCIP_CONSHDLRDATA* conshdlrdata;
608 SCIP_CONSHDLR* conshdlr;
609
610 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
611 conshdlrdata->mipdata = mipdata;
612
613 /* include constraint handler */
614 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
615 -1000000, -1000000, 100, FALSE,
616 consEnfolpViolatedCuts, consEnfopsViolatedCuts, consCheckViolatedCuts, consLockViolatedCuts,
617 conshdlrdata) );
618
619 assert(conshdlr != NULL);
620
621 /* set non-fundamental callbacks via specific setter functions */
622 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeViolatedCuts) );
623
624 return SCIP_OKAY;
625}
626
627
628/*
629 * local methods
630 */
631
632
633/** stores nonzero elements of dense coefficient vector as sparse vector and calculates activity and norm
634 *
635 * copied from sepa_gomory.c
636 */
637static
638SCIP_RETCODE storeCutInArrays(
639 SCIP* scip, /**< SCIP data structure */
640 int nvars, /**< number of problem variables */
641 SCIP_Real* cutcoefs, /**< dense coefficient vector */
642 SCIP_Real* varsolvals, /**< dense variable LP solution vector */
643 char normtype, /**< type of norm to use for efficacy norm calculation */
644 int* cutinds, /**< array to store variables of sparse cut vector */
645 SCIP_Real* cutvals, /**< array to store coefficients of sparse cut vector */
646 int* cutlen, /**< pointer to store number of nonzero entries in cut */
647 SCIP_Real* cutact, /**< pointer to store activity of cut */
648 SCIP_Real* cutnorm /**< pointer to store norm of cut vector */
649 )
650{
651 SCIP_Real val;
652 SCIP_Real cutsqrnorm;
653 SCIP_Real act;
654 SCIP_Real norm;
655 int len;
656 int v;
657
658 assert( nvars == 0 || cutcoefs != NULL );
659 assert( nvars == 0 || varsolvals != NULL );
660 assert( cutinds != NULL );
661 assert( cutvals != NULL );
662 assert( cutlen != NULL );
663 assert( cutact != NULL );
664 assert( cutnorm != NULL );
665
666 len = 0;
667 act = 0.0;
668 norm = 0.0;
669 switch ( normtype )
670 {
671 case 'e':
672 cutsqrnorm = 0.0;
673 for (v = 0; v < nvars; ++v)
674 {
675 val = cutcoefs[v];
676 if ( !SCIPisZero(scip, val) )
677 {
678 act += val * varsolvals[v];
679 cutsqrnorm += SQR(val);
680 cutinds[len] = v;
681 cutvals[len++] = val;
682 }
683 }
684 norm = sqrt(cutsqrnorm);
685 break;
686 case 'm':
687 for (v = 0; v < nvars; ++v)
688 {
689 val = cutcoefs[v];
690 if ( !SCIPisZero(scip, val) )
691 {
692 act += val * varsolvals[v];
693 if ( REALABS(val) > norm )
694 norm = REALABS(val);
695 cutinds[len] = v;
696 cutvals[len++] = val;
697 }
698 }
699 break;
700 case 's':
701 for (v = 0; v < nvars; ++v)
702 {
703 val = cutcoefs[v];
704 if ( !SCIPisZero(scip, val) )
705 {
706 act += val * varsolvals[v];
707 norm += REALABS(val);
708 cutinds[len] = v;
709 cutvals[len++] = val;
710 }
711 }
712 break;
713 case 'd':
714 for (v = 0; v < nvars; ++v)
715 {
716 val = cutcoefs[v];
717 if ( !SCIPisZero(scip, val) )
718 {
719 act += val * varsolvals[v];
720 cutinds[len] = v;
721 cutvals[len++] = val;
722 }
723 }
724 if ( len > 0 )
725 norm = 1.0;
726 break;
727 default:
728 SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", normtype);
729 return SCIP_INVALIDDATA;
730 }
731
732 *cutlen = len;
733 *cutact = act;
734 *cutnorm = norm;
735
736 return SCIP_OKAY;
737}
738
739
740/** Compute lhs/rhs for transformed column
741 *
742 * Consider a variable \f$x_j\f$ and some row of the original system:
743 * \f[
744 * \gamma \leq a^T x \leq \delta, \quad \ell_j \leq x_j \leq u_j.
745 * \f]
746 * We perform the transformation
747 * \f[
748 * x_i' = \left\{
749 * \begin{array}{ll}
750 * s + \frac{1}{\sigma}\, x_j & \mbox{if }i = j\\
751 * x_i & \mbox{otherwise},
752 * \end{array}
753 * \right.
754 * \f]
755 * where \f$s\f$ is the offset value and \f$\sigma\f$ is a scaling factor. The new system is
756 * \f[
757 * \gamma + \sigma\, a_j\,s \leq \sum_{i \neq j} a_i\, x_i' + \sigma a_j\, x_j' \leq \delta + \sigma\, a_j\, s
758 * \f]
759 * with bounds
760 * \f[
761 * \frac{1}{\sigma} \ell_j + s \leq x_j' \leq \frac{1}{\sigma} u_j + s, \qquad \mbox{ if }\sigma > 0
762 * \f]
763 * and
764 * \f[
765 * \frac{1}{\sigma} u_j + s \leq x_j' \leq \frac{1}{\sigma} \ell_j + s, \qquad \mbox{ if }\sigma < 0.
766 * \f]
767 *
768 * This can be used as follows:
769 *
770 * - If \f$x_j \geq \ell_j\f$ has a (nonzero) lower bound, one can use \f$s = -\ell_j\f$, \f$\sigma = 1\f$,
771 * and obtain \f$\gamma - a_j\,\ell_j \leq a^T x' \leq \delta - a_j\,\ell_j\f$, \f$0 \leq x_j' \leq u_j - \ell_j\f$.
772 *
773 * - If \f$x_j \leq u_j\f$ has a (nonzero) upper bound, one can use \f$s = u_j\f$, \f$\sigma = -1\f$,
774 * and obtain \f$\gamma - a_j\,u_j \leq \sum_{i \neq j} a_i\, x_i' - a_j\, x_j' \leq \delta - a_j\, u_j\f$,
775 * \f$0 \leq x_j' \leq u_j - \ell_j\f$.
776 */
777static
778SCIP_RETCODE transformColumn(
779 SCIP* scip, /**< SCIP data structure */
780 SCIP_SEPADATA* sepadata, /**< separator data */
781 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
782 SCIP_COL* col, /**< column that should be complemented */
783 SCIP_Real offset, /**< offset by which column should be shifted */
784 SCIP_Real sigma, /**< scaling factor */
785 SCIP_Real* lhs, /**< array of lhs of rows */
786 SCIP_Real* rhs, /**< array rhs of rows */
787 SCIP_Real* lb, /**< pointer to lb of column */
788 SCIP_Real* ub, /**< pointer to ub of column */
789 SCIP_Real* primsol /**< pointer to solution value */
790 )
791{
792 SCIP_ROW** colrows;
793 SCIP_Real* colvals;
794 int pos, i;
795
796 assert( scip != NULL );
797 assert( lhs != NULL );
798 assert( rhs != NULL );
799 assert( col != NULL );
800
801 colrows = SCIPcolGetRows(col);
802 colvals = SCIPcolGetVals(col);
803 assert( SCIPcolGetNLPNonz(col) == 0 || colrows != NULL );
804 assert( SCIPcolGetNLPNonz(col) == 0 || colvals != NULL );
805 assert( ! SCIPisZero(scip, sigma) );
806
807 /* loop through rows that contain column */
808 for (i = 0; i < SCIPcolGetNLPNonz(col); ++i)
809 {
810 SCIP_ROW* row;
811
812 row = colrows[i];
813 assert( row != NULL );
814
815 /* skip modifiable rows and local rows, unless allowed */
816 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
817 continue;
818
819 pos = SCIProwGetLPPos(row);
820 assert( 0 <= pos && pos < (int) mipdata->nrows );
821
822 assert( ! SCIPisInfinity(scip, lhs[pos]) );
823 if ( ! SCIPisInfinity(scip, -lhs[pos]) )
824 lhs[pos] += sigma * colvals[i] * offset;
825
826 assert( ! SCIPisInfinity(scip, -rhs[pos]) );
827 if ( ! SCIPisInfinity(scip, rhs[pos]) )
828 rhs[pos] += sigma * colvals[i] * offset;
829 }
830
831 /* check objective function */
832 if ( sepadata->useobjub || sepadata->useobjlb )
833 {
834 assert( SCIPisEQ(scip, SCIPcolGetObj(col), SCIPvarGetObj(SCIPcolGetVar(col))) );
835 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
836
837 if ( ! SCIPisInfinity(scip, -lhs[mipdata->nrows]) )
838 lhs[mipdata->nrows] += sigma * SCIPcolGetObj(col) * offset;
839
840 if ( ! SCIPisInfinity(scip, rhs[mipdata->nrows]) )
841 rhs[mipdata->nrows] += sigma * SCIPcolGetObj(col) * offset;
842 }
843
844 /* correct lower and upper bounds and solution */
845 if ( SCIPisNegative(scip, sigma) )
846 {
847 SCIP_Real l;
848
849 assert( ! SCIPisInfinity(scip, -*ub) );
850 if ( ! SCIPisInfinity(scip, *ub) )
851 l = *ub/sigma + offset;
852 else
853 l = -SCIPinfinity(scip);
854
855 assert( ! SCIPisInfinity(scip, *lb) );
856 if ( ! SCIPisInfinity(scip, -*lb) )
857 *ub = *lb/sigma + offset;
858 else
859 *ub = SCIPinfinity(scip);
860 *lb = l;
861 }
862 else
863 {
864 assert( ! SCIPisInfinity(scip, *lb) );
865 if ( ! SCIPisInfinity(scip, -*lb) )
866 *lb = *lb/sigma + offset;
867 assert( ! SCIPisInfinity(scip, -*ub) );
868 if ( ! SCIPisInfinity(scip, *ub) )
869 *ub = *ub/sigma + offset;
870 }
871 *primsol = *primsol/sigma + offset;
872
873 return SCIP_OKAY;
874}
875
876
877/** compute objective coefficient for rows that are weighted by size
878 *
879 * The objective is computed by multiplying a default value by
880 * \f[
881 * 1 - (r_{\mbox{max}} - r) \frac{1 - a}{r_{\mbox{max}} - r_{\mbox{min}}},
882 * \f]
883 * where \f$r\f$ is the size of the current row, \f$a \in [0,1]\f$ is a parameter, and \f$r_{\mbox{max}}\f$ and
884 * \f$r_{\mbox{min}}\f$ are the maximal and minimal size of a row, respectively.
885 *
886 * Thus, if \f$r = r_{\mbox{max}}\f$, we get 1 and if \f$r = r_{\mbox{min}}\f$, we get \f$a\f$.
887 */
888static
889SCIP_Real computeObjWeightSize(
890 int rowsize, /**< size of current row */
891 int minrowsize, /**< maximal size of rows */
892 int maxrowsize /**< minimal size of rows */
893 )
894{
895 SCIP_Real a;
896
897 assert( maxrowsize > 0 );
898 assert( minrowsize < INT_MAX );
899 assert( minrowsize <= maxrowsize );
900 assert( minrowsize <= rowsize && rowsize <= maxrowsize );
901
902 if ( minrowsize == maxrowsize )
903 return 1.0;
904
905 a = (1.0 - OBJWEIGHTRANGE)/((SCIP_Real) (maxrowsize - minrowsize));
906
907 return 1.0 - a * ((SCIP_Real) (maxrowsize - rowsize));
908}
909
910
911/** Creates a subscip representing the separating MIP.
912 *
913 * Let the constraints of the original MIP be of the following form:
914 * \f[
915 * \begin{array}{l@{\;}ll}
916 * a \leq A x + & C r & \leq b\\
917 * \ell \leq x & & \leq u\\
918 * c \leq & r & \leq d\\
919 * x \in Z^n.
920 * \end{array}
921 * \f]
922 * Here, some of the bounds may have value \f$\infty\f$ or \f$-\infty\f$. Written in
923 * \f$\leq\f$-form this becomes:
924 * \f[
925 * \begin{array}{r@{\;}l}
926 * \tilde{A} x + \tilde{C} r & \leq \tilde{b}\\
927 * -x & \leq -\ell\\
928 * x & \leq u\\
929 * -r & \leq -c\\
930 * r & \leq d\\
931 * x \in Z^n,
932 * \end{array}
933 * \f]
934 * where we use
935 * \f[
936 * \tilde{A} =
937 * \left[
938 * \begin{array}{r}
939 * -A \\
940 * A
941 * \end{array}
942 * \right],
943 * \quad
944 * \tilde{C} =
945 * \left[
946 * \begin{array}{r}
947 * - C\\
948 * C
949 * \end{array}
950 * \right]
951 * \qquad\mbox{ and }\qquad
952 * \tilde{b} =
953 * \left[
954 * \begin{array}{r}
955 * -a\\
956 * b
957 * \end{array}
958 * \right].
959 * \f]
960 * For the moment we assume that \f$c = 0\f$, i.e., the lower bounds on the continuous variables
961 * are 0. To obtain a Chv&aacute;tal-Gomory cut we have to find nonnegative multipliers \f$y\f$,
962 * \f$\underline{z}\f$, and \f$\overline{z}\f$ such that
963 * \f[
964 * y^T \tilde{A} - \underline{z}^T + \overline{z}^T \in Z \qquad\mbox{ and }\qquad
965 * y^T \tilde{C} \geq 0.
966 * \f]
967 * Note that we use zero multipliers for the bounds on the continuous variables \f$r\f$. Moreover,
968 * if some bounds are infinity, the corresponding multipliers are assumed to be 0. From these
969 * conditions, we obtain
970 * \f[
971 * (y^T \tilde{A} - \underline{z}^T + \overline{z}^T)\, x +
972 * y^T \tilde{C} \, r \leq
973 * y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u.
974 * \f]
975 * Because \f$r \geq 0\f$, we can ignore the term \f$y^T \tilde{C} \, r \geq 0\f$ and obtain the
976 * following cut:
977 * \f[
978 * (y^T \tilde{A} - \underline{z}^T + \overline{z}^T )\, x \leq
979 * \lfloor y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u \rfloor.
980 * \f]
981 * Assume that \f$\ell = 0\f$ for the meantime. Then the cut can be written as:
982 * \f[
983 * \lfloor y^T \tilde{A} + \overline{z}^T \rfloor \, x \leq
984 * \lfloor y^T \tilde{b} + \overline{z}^T u \rfloor.
985 * \f]
986 *
987 * Following Fischetti and Lodi [2005], let \f$(x^*,r^*)\f$ be a fractional solution of the above
988 * original system. The separating MIP created below is
989 * \f[
990 * \begin{array}{rlr@{\;}l}
991 * \max & (x^*)^T \alpha - \beta - w^T y \\
992 * & f = \tilde{A}^T y + \overline{z} - \alpha \\
993 * & \tilde{f} = \tilde{b}^T y + u^T \overline{z} - \beta\\
994 * & \tilde{C}^T y \geq 0\\
995 * & 0 \leq f \leq 1 - \epsilon \\
996 * & 0 \leq \tilde{f} \leq 1 - \epsilon\\
997 * & 0 \leq y, \overline{z} \leq 1 - \epsilon.\\
998 * & \alpha \in Z^m, \beta \in Z.
999 * \end{array}
1000 * \f]
1001 * Here, \f$w\f$ is a weight vector; it's idea is to make the sum over all components of \f$y\f$ as
1002 * small as possible, in order to generate sparse cuts.
1003 *
1004 * We perform the following additional computations:
1005 *
1006 * - If the lower bounds on \f$x_i\f$ or \f$r_j\f$ are finite, we shift the variable to have a zero
1007 * lower bound, i.e., we replace it by \f$x_i - \ell_i\f$ (or \f$r_j - u_j\f$). This is helpful in
1008 * several ways: As seen above, the resulting inequalities/formulations simplify. Moreover, it
1009 * allows to drop a variable if \f$x^*_i = 0\f$, see the next comment. If the lower bounds are not
1010 * finite, but the upper bounds are finite, we can complement the variable. If the variables are
1011 * free, the above formulation changes as follows: For free continuous variables, we require
1012 * \f$\tilde{C}^T y = 0\f$. For a free integer variable \f$x_j\f$ (which rarely occurs in
1013 * practice), we require \f$f_j = 0\f$, i.e., we force that \f$(\tilde{A}^T y + \overline{z})_j =
1014 * \alpha_j\f$.
1015 *
1016 * - If \f$x^*_j = 0 = \ell_j\f$ (after the above preprocessing), we drop variable \f$\alpha_j\f$
1017 * from the formulation. Let \f$(\alpha^*, \beta^*, y^*, \overline{z}^*)\f$ be an
1018 * optimal solution to the separating MIP. Then we can compute \f$\alpha_j =
1019 * \lfloor(\tilde{A}_j^T y^* + \overline{z}^*)\rfloor\f$.
1020 *
1021 * - If \f$x^*_i = u_i\f$, we complement the variable and drop it from the formulation, since the
1022 * lower bound is 0 afterwards.
1023 *
1024 * - If a variable has been shifted or complemented, we have to recompute \f$\beta\f$ with the
1025 * original lhs/rhs.
1026 *
1027 * - If a continuous variable \f$r_j\f$ is free, we have to force equality for the corresponding components in
1028 * \f$y^T \tilde{C} \, r \geq 0\f$.
1029 *
1030 * - If an integer variable \f$x_i\f$ is free, we are not allowed to round the cut down. In this
1031 * case, the combintation of rows and bounds has to be integral. We force this by requiring that
1032 * \f$f_i = 0\f$.
1033 *
1034 * - If @p contconvert is true, some integral variables are randomly treated as if they were
1035 * continuous. This has the effect that in the resulting cut the corresponding coefficient has
1036 * value 0. This makes the cuts more sparse. Moreover, the separation problems should become
1037 * easier.
1038 *
1039 * - If required, i.e., parameter @p primalseparation is true, we force a primal separation step. For
1040 * this we require that the cut is tight at the currently best solution. To get reliable solutions
1041 * we relax equality by EPSILONVALUE.
1042 *
1043 * - If required (via parameters @p useobjub or @p useobjlb), we add a row corresponding to the objective function with
1044 * respect to the current lower and upper bounds.
1045 */
1046static
1047SCIP_RETCODE createSubscip(
1048 SCIP* origscip, /**< SCIP data structure */
1049 SCIP_SEPA* sepa, /**< separator */
1050 SCIP_SEPADATA* sepadata, /**< separator data */
1051 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
1052 )
1053{
1054 SCIP* subscip;
1055 SCIP_COL** cols;
1056 SCIP_ROW** rows;
1057 SCIP_Real* lhs;
1058 SCIP_Real* rhs;
1059 SCIP_Real* lb;
1060 SCIP_Real* ub;
1061 SCIP_Real* primsol;
1062 SCIP_Real multvarub;
1063
1064 unsigned int cnt;
1065 unsigned int ucnt;
1066 unsigned int nshifted;
1067 unsigned int ncomplemented;
1068#ifndef NDEBUG
1069 unsigned int ncontconverted = 0;
1070 unsigned int nintconverted = 0;
1071#endif
1072 unsigned int nlbounds;
1073 unsigned int nubounds;
1074
1075 SCIP_VAR** consvars;
1076 SCIP_Real* consvals;
1077 SCIP_CONS* cons;
1078 int nconsvars;
1079 char name[SCIP_MAXSTRLEN];
1080
1081 int ncols;
1082 int nrows;
1083 int ntotalrows;
1084 int maxrowsize = 0;
1085 int minrowsize = INT_MAX;
1086 int i, j;
1087
1088 assert( origscip != NULL );
1089 assert( sepadata != NULL );
1090
1091 assert( mipdata->subscip == NULL );
1092
1093 SCIP_CALL( SCIPgetLPColsData(origscip, &cols, &ncols) );
1094 SCIP_CALL( SCIPgetLPRowsData(origscip, &rows, &nrows) );
1095 assert( ncols > 0 && nrows > 0 );
1096
1097 mipdata->m = 0;
1098 mipdata->n = 0;
1099 mipdata->nrows = (unsigned int) nrows;
1100 mipdata->ncols = (unsigned int) ncols;
1101 mipdata->ntotalrows = mipdata->nrows;
1102
1103 if ( sepadata->useobjub || sepadata->useobjlb )
1104 mipdata->ntotalrows = mipdata->nrows + 1;
1105
1106 assert(mipdata->ntotalrows <= INT_MAX);
1107 ntotalrows = (int) mipdata->ntotalrows;
1108
1109 /* copy value */
1110 mipdata->conshdlrusenorm = sepadata->conshdlrusenorm;
1111
1112 /* create subscip */
1113 SCIP_CALL( SCIPcreate( &(mipdata->subscip) ) );
1114 subscip = mipdata->subscip;
1115 SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
1116
1117 /* add violation constraint handler if requested */
1118 if ( sepadata->addviolconshdlr )
1119 {
1120 SCIP_CALL( SCIPincludeConshdlrViolatedCut(subscip, mipdata) );
1121 }
1122
1123 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sepa_cgmip separating MIP (%s)", SCIPgetProbName(origscip));
1124 SCIP_CALL( SCIPcreateProb(subscip, name, NULL, NULL , NULL , NULL , NULL , NULL , NULL) );
1125 SCIPsetSubscipDepth(subscip, SCIPgetSubscipDepth(origscip) + 1);
1126 SCIP_CALL( SCIPsetObjsense(subscip, SCIP_OBJSENSE_MAXIMIZE) );
1127
1128 /* alloc memory for subscipdata elements */
1129 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->alpha), ncols) );
1130 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->fracalpha), ncols) );
1131 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->coltype), ncols) );
1132 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->iscomplemented), ncols) );
1133 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->isshifted), ncols) );
1134 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->ylhs), ntotalrows) );
1135 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->yrhs), ntotalrows) );
1136 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->z), 2*ncols) );
1137 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->lhs), ntotalrows) );
1138 SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->rhs), ntotalrows) );
1139 lhs = mipdata->lhs;
1140 rhs = mipdata->rhs;
1141
1142 /* get temporary storage */
1143 SCIP_CALL( SCIPallocBufferArray(origscip, &lb, ncols) );
1144 SCIP_CALL( SCIPallocBufferArray(origscip, &ub, ncols) );
1145 SCIP_CALL( SCIPallocBufferArray(origscip, &primsol, ncols) );
1146
1147 /* store lhs/rhs for complementing (see below) and compute maximal nonzeros of candidate rows */
1148 for (i = 0; i < nrows; ++i)
1149 {
1150 SCIP_Real val;
1151 SCIP_ROW* row;
1152
1153 row = rows[i];
1154 assert( row != NULL );
1155
1156 val = SCIProwGetLhs(row) - SCIProwGetConstant(row);
1157 if ( SCIProwIsIntegral(row) )
1158 val = SCIPfeasCeil(origscip, val); /* row is integral: round left hand side up */
1159 lhs[i] = val;
1160
1161 val = SCIProwGetRhs(row) - SCIProwGetConstant(row);
1162 if ( SCIProwIsIntegral(row) )
1163 val = SCIPfeasFloor(origscip, val); /* row is integral: round right hand side down */
1164 rhs[i] = val;
1165
1166 /* skip modifiable rows and local rows, unless allowed */
1167 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1168 continue;
1169
1170 /* skip rows that not have been active for a longer time */
1171 if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 && SCIProwGetAge(row) > sepadata->maxrowage )
1172 continue;
1173
1174 /* check whether we want to skip cuts produced by the CGMIP separator */
1175 if ( sepadata->onlyrankone )
1176 {
1177 if ( SCIProwGetOriginSepa(row) == sepa )
1178 continue;
1179 }
1180
1181 /* determine maximal row size: */
1182 val = SCIPgetRowLPActivity(origscip, row);
1183 if ( ! SCIPisInfinity(origscip, REALABS(lhs[i])) )
1184 {
1185 if ( ! sepadata->onlyactiverows || SCIPisFeasEQ(origscip, val, SCIProwGetLhs(row)) )
1186 {
1187 if ( SCIProwGetNLPNonz(row) > maxrowsize )
1188 maxrowsize = SCIProwGetNLPNonz(row);
1189 if ( SCIProwGetNLPNonz(row) < minrowsize )
1190 minrowsize = SCIProwGetNLPNonz(row);
1191 }
1192 }
1193 else
1194 {
1195 if ( ! SCIPisInfinity(origscip, rhs[i]) )
1196 {
1197 if ( ! sepadata->onlyactiverows || SCIPisFeasEQ(origscip, val, SCIProwGetRhs(row)) )
1198 {
1199 if ( SCIProwGetNLPNonz(row) > maxrowsize )
1200 maxrowsize = SCIProwGetNLPNonz(row);
1201 if ( SCIProwGetNLPNonz(row) < minrowsize )
1202 minrowsize = SCIProwGetNLPNonz(row);
1203 }
1204 }
1205 }
1206 }
1207 assert( maxrowsize > 0 );
1208 assert( minrowsize < INT_MAX );
1209
1210 /* add cuts for objective function if required */
1211 if ( sepadata->useobjub )
1212 {
1213 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1214 rhs[mipdata->nrows] = SCIPgetUpperbound(origscip);
1215 assert( ! SCIPisObjIntegral(origscip) || SCIPisFeasIntegral(origscip, SCIPgetUpperbound(origscip)) );
1216
1217 if ( ! SCIPisInfinity(origscip, SCIPgetUpperbound(origscip)) && SCIPgetNObjVars(origscip) > maxrowsize )
1218 maxrowsize = SCIPgetNObjVars(origscip);
1219 if ( ! SCIPisInfinity(origscip, SCIPgetUpperbound(origscip)) && SCIPgetNObjVars(origscip) < minrowsize )
1220 minrowsize = SCIPgetNObjVars(origscip);
1221 }
1222 if ( sepadata->useobjlb )
1223 {
1224 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1225
1226 if ( SCIPisObjIntegral(origscip) )
1227 lhs[mipdata->nrows] = SCIPfeasCeil(origscip, SCIPgetLowerbound(origscip));
1228 else
1229 lhs[mipdata->nrows] = SCIPgetLowerbound(origscip);
1230
1231 if ( ! SCIPisInfinity(origscip, -SCIPgetLowerbound(origscip)) && SCIPgetNObjVars(origscip) > maxrowsize )
1232 maxrowsize = SCIPgetNObjVars(origscip);
1233 if ( ! SCIPisInfinity(origscip, -SCIPgetLowerbound(origscip)) && SCIPgetNObjVars(origscip) < minrowsize )
1234 minrowsize = SCIPgetNObjVars(origscip);
1235 }
1236
1237 /* store lb/ub for complementing and perform preprocessing */
1238 nshifted = 0;
1239 ncomplemented = 0;
1240 nlbounds = 0;
1241 nubounds = 0;
1242 for (j = 0; j < ncols; ++j)
1243 {
1244 SCIP_COL* col;
1245 SCIP_VAR* var;
1246
1247 col = cols[j];
1248 assert( col != NULL );
1249 var = SCIPcolGetVar(col);
1250 assert( var != NULL );
1251
1252 primsol[j] = SCIPcolGetPrimsol(col);
1253 assert( SCIPisEQ(origscip, SCIPgetVarSol(origscip, var), primsol[j]) );
1254
1255 lb[j] = SCIPvarGetLbGlobal(var);
1256 assert( SCIPisEQ(origscip, SCIPvarGetLbLocal(var), SCIPcolGetLb(col)) );
1257
1258 /* if allowed, try to use stronger local bound */
1259 if ( sepadata->allowlocal && SCIPisGT(origscip, SCIPvarGetLbLocal(var), lb[j]) )
1260 lb[j] = SCIPvarGetLbLocal(var);
1261
1262 ub[j] = SCIPvarGetUbGlobal(var);
1263 assert( SCIPisEQ(origscip, SCIPvarGetUbLocal(var), SCIPcolGetUb(col)) );
1264
1265 /* if allowed, try to use stronger local bound */
1266 if ( sepadata->allowlocal && SCIPisLT(origscip, SCIPvarGetUbLocal(var), ub[j]) )
1267 ub[j] = SCIPvarGetUbLocal(var);
1268
1269 mipdata->coltype[j] = colPresent;
1270 mipdata->iscomplemented[j] = FALSE;
1271 mipdata->isshifted[j] = FALSE;
1272
1273 /* check status of column/variable */
1274 if ( SCIPcolIsIntegral(col) )
1275 {
1276 /* integral variables taking integral values are not interesting - will be substituted out below */
1277 if ( ! SCIPisFeasIntegral(origscip, primsol[j]) )
1278 {
1279 /* possibly convert fractional integral variables to take integral values */
1280 if ( sepadata->intconvert && ncols >= sepadata->intconvmin )
1281 {
1282 /* randomly convert variables */
1283 if ( SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->intconvfrac )
1284 {
1285 assert( ! SCIPisInfinity(origscip, ub[j]) || ! SCIPisInfinity(origscip, -lb[j]) );
1286
1287 /* if both bounds are finite, take the closer one */
1288 if ( ! SCIPisInfinity(origscip, ub[j]) && ! SCIPisInfinity(origscip, -lb[j]) )
1289 {
1290 assert( SCIPisFeasIntegral(origscip, ub[j]) );
1291 assert( SCIPisFeasIntegral(origscip, lb[j]) );
1292 assert( SCIPisFeasLT(origscip, primsol[j], ub[j]) );
1293 assert( SCIPisFeasGT(origscip, primsol[j], lb[j]) );
1294 if ( ub[j] - primsol[j] < primsol[j] - lb[j] )
1295 primsol[j] = ub[j];
1296 else
1297 primsol[j] = lb[j];
1298#ifndef NDEBUG
1299 ++nintconverted;
1300#endif
1301 }
1302 else
1303 {
1304 /* if only lower bound is finite */
1305 if ( ! SCIPisInfinity(origscip, -lb[j]) )
1306 {
1307 assert( SCIPisFeasIntegral(origscip, lb[j]) );
1308 primsol[j] = lb[j];
1309#ifndef NDEBUG
1310 ++nintconverted;
1311#endif
1312 }
1313 else
1314 {
1315 assert( ! SCIPisInfinity(origscip, ub[j]) );
1316 assert( SCIPisFeasIntegral(origscip, ub[j]) );
1317 primsol[j] = ub[j];
1318#ifndef NDEBUG
1319 ++nintconverted;
1320#endif
1321 }
1322 }
1323 }
1324 }
1325 }
1326
1327 /* integral variables taking integral values are not interesting - will be substituted out below */
1328 if ( ! SCIPisFeasIntegral(origscip, primsol[j]) )
1329 {
1330 /* possibly convert integral variables to be continuous */
1331 if ( sepadata->contconvert && ncols >= sepadata->contconvmin )
1332 {
1333 /* randomly convert variables */
1334 if ( SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->contconvfrac )
1335 {
1336 /* preprocessing is also performed for converted columns */
1337 mipdata->coltype[j] = colConverted;
1338#ifndef NDEBUG
1339 ++ncontconverted;
1340#endif
1341 }
1342 }
1343 }
1344 }
1345 else
1346 {
1347 /* detect continuous variables, but perform preprocessing for them */
1348 mipdata->coltype[j] = colContinuous;
1349 }
1350
1351 /* if integer variable is at its upper bound -> complementing (this also generates a 0 lower bound) */
1352 if ( mipdata->coltype[j] == colPresent && SCIPisFeasEQ(origscip, primsol[j], ub[j]) )
1353 {
1354 assert( ! SCIPisInfinity(origscip, ub[j]) );
1355 SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1356 mipdata->iscomplemented[j] = TRUE;
1357 mipdata->coltype[j] = colAtUb;
1358 ++nubounds;
1359 }
1360 else
1361 {
1362 /* if a variable has a finite nonzero lower bound -> shift */
1363 if ( ! SCIPisInfinity(origscip, -lb[j]) )
1364 {
1365 if ( ! SCIPisZero(origscip, lb[j]) )
1366 {
1367 SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, -lb[j], 1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1368 assert( SCIPisZero(origscip, lb[j]) );
1369 mipdata->isshifted[j] = TRUE;
1370 ++nshifted;
1371 }
1372
1373 /* if integer variable is at its lower bound */
1374 if ( mipdata->coltype[j] == colPresent && SCIPisZero(origscip, primsol[j]) )
1375 {
1376 mipdata->coltype[j] = colAtLb;
1377 ++nlbounds;
1378 }
1379 }
1380 else
1381 {
1382 /* lower bound is minus-infinity -> check whether upper bound is finite */
1383 if ( ! SCIPisInfinity(origscip, ub[j]) )
1384 {
1385 /* complement variable */
1386 SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1387 assert( SCIPisZero(origscip, lb[j]) );
1388 mipdata->iscomplemented[j] = TRUE;
1389 ++ncomplemented;
1390
1391 /* if integer variable is at its lower bound */
1392 if ( mipdata->coltype[j] == colPresent && SCIPisZero(origscip, primsol[j]) )
1393 {
1394 mipdata->coltype[j] = colAtLb;
1395 ++nlbounds;
1396 }
1397 }
1398 }
1399 }
1400
1401 assert( SCIPisFeasLE(origscip, lb[j], primsol[j]) );
1402 assert( SCIPisFeasLE(origscip, primsol[j], ub[j]) );
1403 }
1404
1405#ifndef NDEBUG
1406 if ( sepadata->intconvert && ncols >= sepadata->intconvmin )
1407 {
1408 SCIPdebugMsg(origscip, "Converted %u fractional integral variables to have integral value.\n", nintconverted);
1409 }
1410 if ( sepadata->contconvert && ncols >= sepadata->contconvmin )
1411 {
1412 SCIPdebugMsg(origscip, "Converted %u integral variables to be continuous.\n", ncontconverted);
1413 }
1414#endif
1415 SCIPdebugMsg(origscip, "Original variables: %d integral, %d continuous, %u shifted, %u complemented, %u at lb, %u at ub\n",
1416 SCIPgetNBinVars(origscip) + SCIPgetNIntVars(origscip) + SCIPgetNImplVars(origscip), SCIPgetNContVars(origscip),
1417 nshifted, ncomplemented, nlbounds, nubounds);
1418
1419 /* prepare upper bound on y-variables */
1420 if ( sepadata->skipmultbounds )
1421 multvarub = SCIPinfinity(origscip);
1422 else
1423 multvarub = 1.0 - EPSILONVALUE;
1424
1425 /* create artificial variables for row combinations (y-variables) */
1426 cnt = 0;
1427 for (i = 0; i < nrows; ++i)
1428 {
1429 SCIP_ROW* row;
1430
1431 row = rows[i];
1432 assert( row != NULL );
1433
1434 mipdata->ylhs[i] = NULL;
1435 mipdata->yrhs[i] = NULL;
1436
1437 /* skip modifiable rows and local rows, unless allowed */
1438 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1439 continue;
1440
1441 /* skip rows that not have been active for a longer time */
1442 if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 && SCIProwGetAge(row) > sepadata->maxrowage )
1443 continue;
1444
1445 /* check whether we want to skip cuts produced by the CGMIP separator */
1446 if ( sepadata->onlyrankone )
1447 {
1448 if ( SCIProwGetOriginSepa(row) == sepa )
1449 continue;
1450 }
1451
1452 /* if we have an equation */
1453 if ( SCIPisEQ(origscip, lhs[i], rhs[i]) )
1454 {
1455 SCIP_Real weight = -sepadata->objweight;
1456
1457 assert( ! SCIPisInfinity(origscip, rhs[i]) );
1458 assert( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetLhs(row)) ); /* equations should always be active */
1459 assert( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetRhs(row)) );
1460
1461 if ( sepadata->objweightsize )
1462 weight = - sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
1463
1464 /* create two variables for each equation */
1465 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yeq1_%d", i);
1466 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[i]), name, 0.0, multvarub,
1467 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1468 SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[i]) );
1469 ++cnt;
1470
1471#ifdef SCIP_MORE_DEBUG
1472 SCIPdebugMsg(origscip, "Created variable <%s> for equation <%s>.\n", name, SCIProwGetName(row));
1473#endif
1474
1475 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yeq2_%d", i);
1476 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[i]), name, 0.0, multvarub,
1477 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1478 SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[i]) );
1479 ++cnt;
1480
1481#ifdef SCIP_MORE_DEBUG
1482 SCIPdebugMsg(origscip, "Created variable <%s> for equation <%s>.\n", name, SCIProwGetName(row));
1483#endif
1484 }
1485 else
1486 {
1487 /* create variable for lhs of row if necessary */
1488 if ( ! SCIPisInfinity(origscip, -lhs[i]) )
1489 {
1490 SCIP_Bool isactive = FALSE;
1491 SCIP_Real weight = 0.0;
1492
1493 /* if the row is active, use objective weight equal to -sepadata->objweight */
1494 if ( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetLhs(row)) )
1495 {
1496 isactive = TRUE;
1497 if ( sepadata->objweightsize )
1498 weight = -sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
1499 else
1500 weight = -sepadata->objweight;
1501 }
1502
1503 if ( ! sepadata->onlyactiverows || isactive )
1504 {
1505 /* add variable */
1506 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ylhs_%d", i);
1507 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[i]), name, 0.0, multvarub,
1508 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1509 SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[i]) );
1510 ++cnt;
1511
1512#ifdef SCIP_MORE_DEBUG
1513 SCIPdebugMsg(origscip, "Created variable <%s> for >= inequality <%s> (weight: %f).\n", name, SCIProwGetName(row), weight);
1514#endif
1515 }
1516 }
1517
1518 /* create variable for rhs of row if necessary */
1519 if ( ! SCIPisInfinity(origscip, rhs[i]) )
1520 {
1521 SCIP_Bool isactive = FALSE;
1522 SCIP_Real weight = 0.0;
1523
1524 /* if the row is active, use objective weight equal to -sepadata->objweight */
1525 if ( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetRhs(row)) )
1526 {
1527 isactive = TRUE;
1528 if ( sepadata->objweightsize )
1529 weight = -sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
1530 else
1531 weight = -sepadata->objweight;
1532 }
1533
1534 if ( ! sepadata->onlyactiverows || isactive )
1535 {
1536 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yrhs_%d", i);
1537 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[i]), name, 0.0, multvarub,
1538 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1539 SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[i]) );
1540 ++cnt;
1541
1542#ifdef SCIP_MORE_DEBUG
1543 SCIPdebugMsg(origscip, "Created variable <%s> for <= inequality <%s> (weight: %f).\n", name, SCIProwGetName(row), weight);
1544#endif
1545 }
1546 }
1547 }
1548 }
1549 assert( (int) cnt <= 2 * nrows );
1550 mipdata->n += cnt;
1551
1552 /* create artificial variables for objective function (if required) (y-variables) */
1553 if ( sepadata->useobjub || sepadata->useobjlb )
1554 {
1555 SCIP_Real weight = 0.0;
1556
1557 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1558 mipdata->ylhs[mipdata->nrows] = NULL;
1559 mipdata->yrhs[mipdata->nrows] = NULL;
1560 cnt = 0;
1561
1562 if ( sepadata->objweightsize )
1563 weight = -sepadata->objweight * computeObjWeightSize(SCIPgetNObjVars(origscip), minrowsize, maxrowsize);
1564 else
1565 weight = -sepadata->objweight;
1566
1567 /* create variable for upper objective bound if necessary */
1568 if ( sepadata->useobjub && ! SCIPisInfinity(origscip, rhs[mipdata->nrows]) )
1569 {
1570 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yobjub");
1571 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[mipdata->nrows]), name, 0.0, multvarub,
1572 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1573 SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[mipdata->nrows]) );
1574 ++cnt;
1575
1576#ifdef SCIP_MORE_DEBUG
1577 SCIPdebugMsg(origscip, "Created variable <%s> for upper bound on objective (weight: %f).\n", name, weight);
1578#endif
1579 }
1580
1581 /* create variable for lower bound objective if necessary */
1582 if ( sepadata->useobjlb && ! SCIPisInfinity(origscip, -lhs[mipdata->nrows]) )
1583 {
1584 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yobjlb");
1585 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[mipdata->nrows]), name, 0.0, multvarub,
1586 weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1587 SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[mipdata->nrows]) );
1588 ++cnt;
1589
1590#ifdef SCIP_MORE_DEBUG
1591 SCIPdebugMsg(origscip, "Created variable <%s> for lower bound on objective (weight: %f).\n", name, weight);
1592#endif
1593 }
1594
1595 assert( (int) cnt <= 2 * ntotalrows );
1596 mipdata->n += cnt;
1597 }
1598
1599 /* create alpha, bound, and fractional variables */
1600 cnt = 0;
1601 ucnt = 0;
1602 for (j = 0; j < ncols; ++j)
1603 {
1604 mipdata->z[j] = NULL;
1605 mipdata->alpha[j] = NULL;
1606 mipdata->fracalpha[j] = NULL;
1607
1608 if ( mipdata->coltype[j] == colPresent )
1609 {
1610 SCIP_Real obj;
1611
1612 if ( sepadata->objlone )
1613 obj = 0.0;
1614 else
1615 obj = primsol[j];
1616
1617 /* create alpha variables */
1618 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "alpha_%d", j);
1619 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->alpha[j]), name, -sepadata->cutcoefbnd, sepadata->cutcoefbnd, obj,
1620 SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1621 SCIP_CALL( SCIPaddVar(subscip, mipdata->alpha[j]) );
1622 ++cnt;
1623
1624 /* create fractional variables */
1625 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "f_%d", j);
1626 if ( SCIPisInfinity(origscip, -lb[j]) && SCIPisInfinity(origscip, ub[j]) )
1627 {
1628 /* fix fractional value to be zero for free original variables */
1629 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracalpha[j]), name, 0.0, 0.0, 0.0,
1630 SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1631 }
1632 else
1633 {
1634 /* fractional value in [0, 1) for variables with finite bounds */
1635 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracalpha[j]), name, 0.0, 1.0-EPSILONVALUE, 0.0,
1636 SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1637 }
1638 SCIP_CALL( SCIPaddVar(subscip, mipdata->fracalpha[j]) );
1639 ++cnt;
1640
1641 /* create variables for upper bounds */
1642 if ( ! SCIPisInfinity(origscip, ub[j]) )
1643 {
1644 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "zub_%d", j);
1645 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->z[j]), name, 0.0, multvarub,
1646 0.0, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1647 SCIP_CALL( SCIPaddVar(subscip, mipdata->z[j]) );
1648 ++ucnt;
1649 }
1650 }
1651 }
1652 assert( (int) cnt <= 2 * ncols );
1653 assert( (int) ucnt <= ncols );
1654
1655 /* create variable for the rhs of the cut */
1656 if ( sepadata->objlone )
1657 {
1658 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, 0.0,
1659 SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1660 }
1661 else
1662 {
1663 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, -1.0,
1664 SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1665 }
1666 SCIP_CALL( SCIPaddVar(subscip, mipdata->beta) );
1667
1668 /* create fractional variable for the rhs */
1669 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracbeta), "fracbeta", 0.0, 1.0-BETAEPSILONVALUE, 0.0,
1670 SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1671 SCIP_CALL( SCIPaddVar(subscip, mipdata->fracbeta) );
1672 mipdata->n += cnt + ucnt + 2;
1673
1674 /* get temporary storage */
1675 SCIP_CALL( SCIPallocBufferArray(origscip, &consvals, (int) mipdata->n) );
1676 SCIP_CALL( SCIPallocBufferArray(origscip, &consvars, (int) mipdata->n) );
1677
1678 /* create constraints for alpha variables of CG-cut */
1679 cnt = 0;
1680 for (j = 0; j < ncols; ++j)
1681 {
1682 SCIP_ROW** colrows;
1683 SCIP_Real* colvals;
1684
1685 /* create ordinary part for all selected variables */
1686 if ( mipdata->coltype[j] == colPresent )
1687 {
1688 SCIP_Real sigma;
1689
1690 assert( cols[j] != NULL );
1691 colrows = SCIPcolGetRows(cols[j]);
1692 colvals = SCIPcolGetVals(cols[j]);
1693 nconsvars = 0;
1694
1695 if ( mipdata->iscomplemented[j] )
1696 sigma = -1.0;
1697 else
1698 sigma = 1.0;
1699
1700 /* add part for columns */
1701 for (i = 0; i < SCIPcolGetNLPNonz(cols[j]); ++i)
1702 {
1703 SCIP_ROW* row;
1704 int pos;
1705
1706 row = colrows[i];
1707 assert( row != NULL );
1708
1709 /* skip modifiable rows and local rows, unless allowed */
1710 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1711 continue;
1712
1713 pos = SCIProwGetLPPos(row);
1714 assert( 0 <= pos && pos < nrows );
1715
1716 if ( mipdata->ylhs[pos] != NULL )
1717 {
1718 consvars[nconsvars] = mipdata->ylhs[pos];
1719 consvals[nconsvars] = -sigma * colvals[i];
1720 ++nconsvars;
1721 }
1722 if ( mipdata->yrhs[pos] != NULL )
1723 {
1724 consvars[nconsvars] = mipdata->yrhs[pos];
1725 consvals[nconsvars] = sigma * colvals[i];
1726 ++nconsvars;
1727 }
1728 assert( nconsvars <= (int) mipdata->n );
1729 }
1730 /* add part for upper bounds */
1731 if ( mipdata->z[j] != NULL )
1732 {
1733 assert( ! SCIPisInfinity(origscip, ub[j]) );
1734 consvars[nconsvars] = mipdata->z[j];
1735 consvals[nconsvars] = 1.0;
1736 ++nconsvars;
1737 }
1738 assert( nconsvars <= (int) mipdata->n );
1739
1740 /* add alpha variable */
1741 consvars[nconsvars] = mipdata->alpha[j];
1742 consvals[nconsvars] = -1.0;
1743 ++nconsvars;
1744 assert( nconsvars <= (int) mipdata->n );
1745
1746 /* add fractional-alpha variable */
1747 consvars[nconsvars] = mipdata->fracalpha[j];
1748 consvals[nconsvars] = -1.0;
1749 ++nconsvars;
1750 assert( nconsvars <= (int) mipdata->n );
1751
1752 /* check for lower and upper objective bounds */
1753 if ( (sepadata->useobjub || sepadata->useobjlb) && ! SCIPisZero(origscip, SCIPcolGetObj(cols[j])) )
1754 {
1755 /* add lower objective bound */
1756 if ( mipdata->ylhs[mipdata->nrows] != NULL )
1757 {
1758 assert( sepadata->useobjlb );
1759 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1760 consvals[nconsvars] = -sigma * SCIPcolGetObj(cols[j]);
1761 ++nconsvars;
1762 }
1763
1764 /* add upper objective bound */
1765 if ( mipdata->yrhs[mipdata->nrows] != NULL )
1766 {
1767 assert( sepadata->useobjub );
1768 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1769 consvals[nconsvars] = sigma * SCIPcolGetObj(cols[j]);
1770 ++nconsvars;
1771 }
1772 }
1773
1774 /* add linear constraint */
1775 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "alpha_%d", j);
1776 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, name, nconsvars, consvars, consvals, 0.0, 0.0,
1777 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1778 SCIP_CALL( SCIPaddCons(subscip, cons) );
1779 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1780 ++cnt;
1781 }
1782 /* generate part that makes sure that cut is valid for continuous variables */
1783 else if ( mipdata->coltype[j] == colContinuous || mipdata->coltype[j] == colConverted )
1784 {
1785 SCIP_Real sigma;
1786 SCIP_Real r;
1787
1788 assert( cols[j] != NULL );
1789 colrows = SCIPcolGetRows(cols[j]);
1790 colvals = SCIPcolGetVals(cols[j]);
1791 nconsvars = 0;
1792
1793 if ( mipdata->iscomplemented[j] )
1794 sigma = -1.0;
1795 else
1796 sigma = 1.0;
1797
1798 /* add part for columns */
1799 for (i = 0; i < SCIPcolGetNLPNonz(cols[j]); ++i)
1800 {
1801 SCIP_ROW* row;
1802 int pos;
1803
1804 row = colrows[i];
1805 assert( row != NULL );
1806
1807 /* skip modifiable rows and local rows, unless allowed */
1808 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1809 continue;
1810
1811 pos = SCIProwGetLPPos(row);
1812 assert( 0 <= pos && pos < nrows );
1813
1814 if ( mipdata->ylhs[pos] != NULL )
1815 {
1816 consvars[nconsvars] = mipdata->ylhs[pos];
1817 consvals[nconsvars] = -sigma * colvals[i];
1818 ++nconsvars;
1819 }
1820 if ( mipdata->yrhs[pos] != NULL )
1821 {
1822 consvars[nconsvars] = mipdata->yrhs[pos];
1823 consvals[nconsvars] = sigma * colvals[i];
1824 ++nconsvars;
1825 }
1826 assert( nconsvars <= (int) mipdata->n );
1827 }
1828
1829 /* check for lower and upper objective bounds */
1830 if ( (sepadata->useobjub || sepadata->useobjlb) && ! SCIPisZero(origscip, SCIPcolGetObj(cols[j])) )
1831 {
1832 /* add lower objective bound */
1833 if ( mipdata->ylhs[mipdata->nrows] )
1834 {
1835 assert( sepadata->useobjlb );
1836 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1837 consvals[nconsvars] = -sigma * SCIPcolGetObj(cols[j]);
1838 ++nconsvars;
1839 }
1840
1841 /* add upper objective bound */
1842 if ( mipdata->yrhs[mipdata->nrows] )
1843 {
1844 assert( sepadata->useobjub );
1845 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1846 consvals[nconsvars] = sigma * SCIPcolGetObj(cols[j]);
1847 ++nconsvars;
1848 }
1849 }
1850
1851 /* add linear constraint */
1852 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cont_%d", j);
1853
1854 /* for free continuous variables require equality */
1855 r = SCIPinfinity(subscip);
1856 if ( SCIPisInfinity(origscip, -lb[j]) && SCIPisInfinity(origscip, ub[j]) )
1857 r = 0.0;
1858 else
1859 assert( SCIPisZero(origscip, lb[j]) );
1860
1861 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, name, nconsvars, consvars, consvals, 0.0, r,
1862 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1863 SCIP_CALL( SCIPaddCons(subscip, cons) );
1864 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1865 ++cnt;
1866 }
1867 }
1868 assert( (int) cnt <= ncols );
1869 mipdata->m += cnt;
1870
1871 /* create constraints for rhs of cut */
1872 nconsvars = 0;
1873
1874 /* first for the rows */
1875 for (i = 0; i < nrows; ++i)
1876 {
1877 assert( rows[i] != NULL );
1878
1879 /* skip modifiable rows and local rows, unless allowed */
1880 if ( SCIProwIsModifiable(rows[i]) || (SCIProwIsLocal(rows[i]) && !sepadata->allowlocal) )
1881 continue;
1882
1883 /* if lhs is there */
1884 if ( mipdata->ylhs[i] != NULL && ! SCIPisZero(origscip, lhs[i]) )
1885 {
1886 assert( ! SCIPisInfinity(origscip, -lhs[i]) );
1887 consvars[nconsvars] = mipdata->ylhs[i];
1888 consvals[nconsvars] = -lhs[i];
1889 ++nconsvars;
1890 }
1891 /* if rhs is there */
1892 if ( mipdata->yrhs[i] != NULL && ! SCIPisZero(origscip, rhs[i]) )
1893 {
1894 assert( ! SCIPisInfinity(origscip, rhs[i]) );
1895 consvars[nconsvars] = mipdata->yrhs[i];
1896 consvals[nconsvars] = rhs[i];
1897 ++nconsvars;
1898 }
1899 assert( nconsvars <= (int) mipdata->n );
1900 }
1901
1902 if ( sepadata->useobjub || sepadata->useobjlb )
1903 {
1904 /* add lower objective bound */
1905 if ( mipdata->ylhs[mipdata->nrows] != NULL && ! SCIPisZero(origscip, lhs[mipdata->nrows]) )
1906 {
1907 assert( sepadata->useobjlb );
1908 assert( ! SCIPisInfinity(origscip, -lhs[mipdata->nrows]) );
1909 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1910 consvals[nconsvars] = -lhs[mipdata->nrows];
1911 ++nconsvars;
1912 }
1913
1914 /* add upper objective bound */
1915 if ( mipdata->yrhs[mipdata->nrows] != NULL && ! SCIPisZero(origscip, rhs[mipdata->nrows]) )
1916 {
1917 assert( sepadata->useobjub );
1918 assert( ! SCIPisInfinity(origscip, rhs[mipdata->nrows]) );
1919 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1920 consvals[nconsvars] = rhs[mipdata->nrows];
1921 ++nconsvars;
1922 }
1923 assert( nconsvars <= (int) mipdata->n );
1924 }
1925
1926 /* next for the columns */
1927 for (j = 0; j < ncols; ++j)
1928 {
1929 /* if ub is there */
1930 if ( mipdata->z[j] != NULL && ! SCIPisZero(origscip, ub[j]) )
1931 {
1932 assert( mipdata->coltype[j] == colPresent );
1933 assert( ! SCIPisInfinity(origscip, ub[j]) );
1934 consvars[nconsvars] = mipdata->z[j];
1935 consvals[nconsvars] = ub[j];
1936 ++nconsvars;
1937 assert( nconsvars <= (int) mipdata->n );
1938 }
1939 }
1940 /* add beta variable */
1941 consvars[nconsvars] = mipdata->beta;
1942 consvals[nconsvars] = -1.0;
1943 ++nconsvars;
1944
1945 /* add fractional-beta variable */
1946 consvars[nconsvars] = mipdata->fracbeta;
1947 consvals[nconsvars] = -1.0;
1948 ++nconsvars;
1949 assert( nconsvars <= (int) mipdata->n );
1950
1951 /* add linear constraint */
1952 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "beta", nconsvars, consvars, consvals, 0.0, 0.0,
1953 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1954 SCIP_CALL( SCIPaddCons(subscip, cons) );
1955 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1956 ++mipdata->m;
1957
1958 /* add primal separation constraint if required */
1959 if ( sepadata->primalseparation )
1960 {
1961 SCIP_SOL* bestsol;
1962 bestsol = SCIPgetBestSol(origscip);
1963 if ( bestsol != NULL )
1964 {
1965 nconsvars = 0;
1966 for (j = 0; j < ncols; ++j)
1967 {
1968 if ( mipdata->alpha[j] != NULL )
1969 {
1970 SCIP_Real val;
1971 assert( mipdata->coltype[j] == colPresent );
1972
1973 val = SCIPgetSolVal(origscip, bestsol, SCIPcolGetVar(cols[j]));
1974 consvars[nconsvars] = mipdata->alpha[j];
1975 consvals[nconsvars] = val;
1976 ++nconsvars;
1977 assert( nconsvars <= (int) mipdata->n );
1978 }
1979 }
1980 consvars[nconsvars] = mipdata->beta;
1981 consvals[nconsvars] = -1.0;
1982 ++nconsvars;
1983
1984 /* add linear constraint - allow slight deviation from equality */
1985 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "primalseparation", nconsvars, consvars, consvals, -EPSILONVALUE, EPSILONVALUE,
1986 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1987 SCIP_CALL( SCIPaddCons(subscip, cons) );
1988 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1989 ++mipdata->m;
1990 }
1991 }
1992
1993 /* add constraint to force violated cuts if required */
1994 if ( sepadata->addviolationcons )
1995 {
1996 nconsvars = 0;
1997 for (j = 0; j < ncols; ++j)
1998 {
1999 if ( mipdata->alpha[j] != NULL )
2000 {
2001 consvars[nconsvars] = mipdata->alpha[j];
2002 consvals[nconsvars] = primsol[j];
2003 ++nconsvars;
2004 assert( nconsvars <= (int) mipdata->n );
2005 }
2006 }
2007 consvars[nconsvars] = mipdata->beta;
2008 consvals[nconsvars] = -1.0;
2009 ++nconsvars;
2010
2011 /* add linear constraint - allow slight deviation from equality */
2012 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "violationConstraint", nconsvars, consvars, consvals, MINEFFICACY, SCIPinfinity(subscip),
2013 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2014 SCIP_CALL( SCIPaddCons(subscip, cons) );
2015 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
2016 ++mipdata->m;
2017 }
2018
2019 SCIPdebugMsg(origscip, "Subscip has %u vars (%d integral, %d continuous), %u conss.\n",
2020 mipdata->n, SCIPgetNIntVars(subscip), SCIPgetNContVars(subscip), mipdata->m);
2021
2022 /* free temporary memory */
2023 SCIPfreeBufferArray(origscip, &consvars);
2024 SCIPfreeBufferArray(origscip, &consvals);
2025
2026 SCIPfreeBufferArray(origscip, &primsol);
2027 SCIPfreeBufferArray(origscip, &lb);
2028 SCIPfreeBufferArray(origscip, &ub);
2029
2030 /* SCIPdebug( SCIP_CALL( SCIPprintOrigProblem(subscip, NULL, NULL, FALSE) ) ); */
2031
2032#ifdef SCIP_WRITEPROB
2033 {
2034 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgsepa%s%s%s%s_%s.lp",
2035 sepadata->objlone ? "_l1" : "",
2036 sepadata->addviolationcons ? "_vc" : "",
2037 sepadata->skipmultbounds ? "_ub" : "",
2038 sepadata->primalseparation ? "_ps" : "",
2039 SCIPgetProbName(origscip));
2040 SCIP_CALL( SCIPwriteOrigProblem(subscip, name, "lp", FALSE) );
2041 SCIPinfoMessage(origscip, NULL, "Wrote subscip to file <%s>.\n", name);
2042 }
2043#endif
2044
2045 return SCIP_OKAY;
2046}
2047
2048
2049/** sets parameters for subscip */
2050static
2051SCIP_RETCODE subscipSetParams(
2052 SCIP_SEPADATA* sepadata, /**< separator data */
2053 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
2054 )
2055{
2056 SCIP* subscip;
2057
2058 assert( sepadata != NULL );
2059 assert( mipdata != NULL );
2060
2061 subscip = mipdata->subscip;
2062 assert( subscip != NULL );
2063
2064 /* set objective limit, if no corresponding constraint has been added */
2065 if ( ! sepadata->addviolationcons && ! sepadata->addviolconshdlr )
2066 {
2067 SCIP_CALL( SCIPsetObjlimit(subscip, MINEFFICACY) );
2068 }
2069
2070 /* do not abort subscip on CTRL-C */
2071 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
2072
2073 /* disable memory saving mode: this is likely to result in the maximal depth being reached. This is because DFS
2074 * results in a repeated branching on the alpha-variables, which often have large bounds resulting in deep levels of
2075 * the tree. */
2076 SCIP_CALL( SCIPsetRealParam(subscip, "memory/savefac", 1.0) );
2077
2078 /* set number of solutions stored */
2079 SCIP_CALL( SCIPsetIntParam(subscip, "limits/maxsol", MAXNSOLS) );
2080
2081 /* determine output to console */
2082#ifdef SCIP_OUTPUT
2083 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2084 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1000) );
2085 SCIP_CALL( SCIPsetIntParam(subscip, "display/nsols/active", 2) );
2086#else
2087 if ( sepadata->output )
2088 {
2089 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2090 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1000) );
2091 SCIP_CALL( SCIPsetIntParam(subscip, "display/nsols/active", 2) );
2092 }
2093 else
2094 {
2095 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
2096 }
2097#endif
2098
2099 if ( sepadata->subscipfast )
2100 {
2101 /* forbid recursive call of plugins solving subMIPs (also disables CG-separation) */
2102#ifdef SCIP_OUTPUT
2103 SCIP_CALL( SCIPsetSubscipsOff(subscip, FALSE) );
2104#else
2105 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); /* quiet */
2106#endif
2107 }
2108 else
2109 {
2110 /* avoid recursive call */
2111 if ( ! SCIPisParamFixed(subscip, "separating/cgmip/freq") )
2112 {
2113 SCIP_CALL( SCIPsetIntParam(subscip, "separating/cgmip/freq", -1) );
2114 }
2115 }
2116
2117#ifdef SCIP_DISABLED_CODE
2118 /* the following possibly helps to improve performance (untested) */
2119 SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) );
2120#else
2121
2122 /* zirounding is often successful, so allow it some more calls */
2123 if ( ! SCIPisParamFixed(subscip, "heuristics/zirounding/minstopncalls") )
2124 {
2125 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/zirounding/minstopncalls", 10000) );
2126 }
2127
2128 if ( sepadata->subscipfast )
2129 {
2130 /* set other heuristics */
2131 if ( ! SCIPisParamFixed(subscip, "heuristics/shifting/freq") )
2132 {
2133 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/shifting/freq", 3) );
2134 }
2135 if ( ! SCIPisParamFixed(subscip, "heuristics/simplerounding/freq") )
2136 {
2137 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/simplerounding/freq", 1) );
2138 }
2139 if ( ! SCIPisParamFixed(subscip, "heuristics/rounding/freq") )
2140 {
2141 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/rounding/freq", 1) );
2142 }
2143 if ( ! SCIPisParamFixed(subscip, "heuristics/oneopt/freq") )
2144 {
2145 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/oneopt/freq", 1) );
2146 }
2147
2148 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/pscostdiving/freq", 1) ); */
2149 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", 3) ); */
2150
2151 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/coefdiving/freq", -1) ); */
2152 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) ); */
2153 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/guideddiving/freq", -1) ); */
2154 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/linesearchdiving/freq", -1) ); */
2155 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/objpscostdiving/freq", -1) ); */
2156 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/rootsoldiving/freq", -1) ); */
2157 /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/veclendiving/freq", -1) ); */
2158
2159 /* use fast presolving */
2160 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
2161
2162 /* disable conflict analysis */
2163 /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useprop", FALSE) ); */
2164 /* SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useinflp", 'o') ); */
2165 /* SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); */
2166 /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usesb", FALSE) ); */
2167 /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usepseudo", FALSE) ); */
2168
2169 /* use fast separation */
2170 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
2171 }
2172#endif
2173
2174#ifdef SCIP_WRITEPROB
2175 {
2176 char name[SCIP_MAXSTRLEN];
2177
2178 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgsepa%s%s%s%s_%s.set",
2179 sepadata->objlone ? "_l1" : "",
2180 sepadata->addviolationcons ? "_vc" : "",
2181 sepadata->skipmultbounds ? "_ub" : "",
2182 sepadata->primalseparation ? "_ps" : "",
2183 SCIPgetProbName(mipdata->scip));
2184 SCIP_CALL( SCIPwriteParams(subscip, name, TRUE, FALSE) );
2185 SCIPinfoMessage(mipdata->scip, NULL, "Wrote settings to file <%s>.\n", name);
2186 }
2187#endif
2188
2189 return SCIP_OKAY;
2190}
2191
2192
2193/** try to convert fractional gomory cuts to primal solutions of CG-MIP */
2194static
2195SCIP_RETCODE createCGMIPprimalsols(
2196 SCIP* scip, /**< original SCIP data structure */
2197 SCIP_SEPADATA* sepadata, /**< separator data */
2198 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
2199 )
2200{
2201 SCIP_VAR** vars;
2202 SCIP_ROW** rows;
2203 SCIP_COL** cols;
2204 SCIP_Real* binvrow;
2205 SCIP_Real* cutcoefs;
2206 int* basisind;
2207 int nvars;
2208 int nrows;
2209 int ncols;
2210 int ngen = 0;
2211 int ntried = 0;
2212 int i;
2213
2214 assert( scip != NULL );
2215 assert( sepadata != NULL );
2216 assert( mipdata != NULL );
2217
2218 /* get variables */
2219 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2220
2221 /* get rows and columns */
2222 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
2223 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
2224 assert( ncols <= nvars );
2225
2226 /* get storage */
2227 SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
2228 SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
2229 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
2230
2231 /* get basis indices */
2232 SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
2233
2234 /* loop through rows */
2235 for (i = 0; i < nrows; ++i)
2236 {
2237 SCIP_Bool tryrow = FALSE;
2238 SCIP_Real primsol = SCIP_INVALID;
2239 int c;
2240 int r;
2241
2242 c = basisind[i];
2243 assert( c < ncols );
2244
2245 if ( c >= 0 )
2246 {
2247 SCIP_VAR* var;
2248
2249 var = SCIPcolGetVar(cols[c]);
2250
2251 if( SCIPvarIsIntegral(var) )
2252 {
2253 primsol = SCIPcolGetPrimsol(cols[c]);
2254 assert( SCIPgetVarSol(scip, var) == primsol ); /*lint !e777*/
2255
2256 if ( SCIPfeasFrac(scip, primsol) >= AWAY && SCIPfeasFrac(scip, primsol) <= 1 - AWAY )
2257 tryrow = TRUE;
2258 }
2259 }
2260#if ( SEPARATEROWS == TRUE )
2261 else
2262 {
2263 SCIP_ROW* row;
2264
2265 assert(0 <= -c-1 && -c-1 < nrows);
2266
2267 row = rows[-c-1];
2268
2269 if ( SCIProwIsIntegral(row) && ! SCIProwIsModifiable(row) )
2270 {
2271 /* Compute value of the slack variable (we only care about the correct fractionality) */
2272 if ( SCIPisInfinity(scip, SCIProwGetRhs(row)) )
2273 primsol = SCIProwGetLhs(row) - SCIPgetRowLPActivity(scip, row);
2274 else
2275 primsol = SCIProwGetRhs(row) - SCIPgetRowLPActivity(scip, row);
2276
2277 if ( SCIPfeasFrac(scip, primsol) >= AWAY && SCIPfeasFrac(scip, primsol) <= 1 - AWAY )
2278 tryrow = TRUE;
2279 }
2280 }
2281#endif
2282
2283 if ( tryrow )
2284 {
2285 SCIP_Bool success;
2286 SCIP_SOL* sol;
2287 SCIP_Real cutrhs = 0.0;
2288 SCIP_ROW* row;
2289 SCIP_Real val;
2290 int j;
2291
2292 assert( primsol != SCIP_INVALID ); /*lint !e777*/
2293
2294 /* get the row of B^-1 for this basic integer variable with fractional solution value */
2295 SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow, NULL, NULL) );
2296
2297 /* clear cutcoefs */
2298 BMSclearMemoryArray(cutcoefs, ncols);
2299
2300 /* create solution */
2301 SCIP_CALL( SCIPcreateSol(mipdata->subscip, &sol, NULL) );
2302
2303 /* add values of multipliers to solution and compute coefficients */
2304 for (r = 0; r < nrows; ++r)
2305 {
2306 SCIP_COL** rowcols;
2307 SCIP_Real* rowvals;
2308 SCIP_Real binvval;
2309 SCIP_Real weight;
2310
2311 row = rows[r];
2312 assert( row != NULL );
2313
2314 binvval = binvrow[r];
2315 binvval = SCIPfrac(scip, binvval); /* can always take fractional value */
2316 if ( ! SCIPisFeasZero(scip, binvval) )
2317 {
2318 SCIP_Real lhs;
2319 SCIP_Real rhs;
2320 SCIP_Bool uselhs;
2321
2322 lhs = SCIProwGetLhs(row);
2323 rhs = SCIProwGetRhs(row);
2324
2325 if ( ! SCIPisEQ(scip, lhs, rhs) )
2326 {
2327 SCIP_BASESTAT stat;
2328
2329 stat = SCIProwGetBasisStatus(row);
2330
2331 if ( stat == SCIP_BASESTAT_LOWER )
2332 {
2333 assert( ! SCIPisInfinity(scip, -lhs) );
2334 uselhs = TRUE;
2335 }
2336 else if ( stat == SCIP_BASESTAT_UPPER )
2337 {
2338 assert( ! SCIPisInfinity(scip, rhs) );
2339 uselhs = FALSE;
2340 }
2341 else if ( SCIPisInfinity(scip, rhs) )
2342 uselhs = TRUE;
2343 else
2344 uselhs = FALSE;
2345 }
2346 else if ( binvval < 0.0 )
2347 uselhs = TRUE;
2348 else
2349 uselhs = FALSE;
2350
2351 if ( uselhs )
2352 {
2353 assert( mipdata->ylhs[r] != NULL );
2354 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->ylhs[r], fabs(binvval)) );
2355 weight = -fabs(binvval);
2356 }
2357 else
2358 {
2359 assert( mipdata->yrhs[r] != NULL );
2360 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->yrhs[r], fabs(binvval)) );
2361 weight = fabs(binvval);
2362 }
2363
2364 /* update cut coefficients */
2365 rowcols = SCIProwGetCols(row);
2366 rowvals = SCIProwGetVals(row);
2367
2368 /* add the row coefficients to the sum */
2369 for (j = 0; j < SCIProwGetNLPNonz(row); ++j)
2370 {
2371 int idx;
2372
2373 assert( rowcols[j] != NULL );
2374
2375 idx = SCIPcolGetLPPos(rowcols[j]);
2376 assert( 0 <= idx && idx < ncols );
2377
2378 cutcoefs[idx] += weight * rowvals[j];
2379 }
2380
2381 /* compute rhs */
2382 if ( uselhs )
2383 {
2384 assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
2385 val = mipdata->lhs[r];
2386 }
2387 else
2388 {
2389 assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) );
2390 val = mipdata->rhs[r];
2391 }
2392 cutrhs += weight * val;
2393 }
2394 }
2395
2396 /* fill in values of cut */
2397 for (c = 0; c < ncols; ++c)
2398 {
2399 if ( mipdata->coltype[c] != colPresent )
2400 continue;
2401
2402 val = SCIPfloor(scip, cutcoefs[c]);
2403 if ( mipdata->iscomplemented[c] )
2404 val = -val;
2405 if ( ! SCIPisFeasZero(scip, val) )
2406 {
2407 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->alpha[c], val) );
2408 }
2409 val = SCIPfeasFrac(scip, cutcoefs[c]);
2410 if ( ! SCIPisFeasZero(scip, val) )
2411 {
2412 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->fracalpha[c], val) );
2413 }
2414 }
2415
2416 if ( ! SCIPisFeasZero(scip, SCIPfloor(scip, cutrhs)) )
2417 {
2418 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->beta, SCIPfloor(scip, cutrhs)) );
2419 }
2420 if ( ! SCIPisFeasZero(scip, SCIPfeasFrac(scip, cutrhs)) )
2421 {
2422 SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->fracbeta, SCIPfeasFrac(scip, cutrhs)) );
2423 }
2424
2425 SCIP_CALL( SCIPtrySolFree(mipdata->subscip, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
2426 ++ntried;
2427 if ( success )
2428 ++ngen;
2429 }
2430 }
2431
2432 SCIPfreeBufferArray(scip, &cutcoefs);
2433 SCIPfreeBufferArray(scip, &binvrow);
2434 SCIPfreeBufferArray(scip, &basisind);
2435
2436 SCIPdebugMsg(scip, "Created %d primal solutions for CG-MIP from tableau cuts (tried: %d).\n", ngen, ntried);
2437
2438 return SCIP_OKAY;
2439}
2440
2441
2442/** solve subscip */
2443static
2444SCIP_RETCODE solveSubscip(
2445 SCIP* origscip, /**< SCIP data structure */
2446 SCIP_SEPADATA* sepadata, /**< separator data */
2447 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
2448 SCIP_Bool* success /**< if setting was successful -> stop */
2449 )
2450{
2451 SCIP* subscip;
2452 SCIP_RETCODE retcode;
2453 SCIP_STATUS status;
2454 SCIP_Real timelimit;
2455 SCIP_Real memorylimit;
2456 SCIP_Longint nodelimit;
2457
2458 assert( origscip != NULL );
2459 assert( sepadata != NULL );
2460 assert( mipdata != NULL );
2461 assert( success != NULL );
2462
2463 *success = TRUE;
2464
2465 subscip = mipdata->subscip;
2466
2467 SCIP_CALL( SCIPcheckCopyLimits(origscip, success) );
2468
2469 if ( ! (*success) )
2470 return SCIP_OKAY;
2471
2472 /* @todo Check whether copying the parameters is useful */
2473 /* SCIP_CALL( SCIPcopyLimits(origscip, subscip) ); */
2474
2475 /* determine time limit */
2476 SCIP_CALL( SCIPgetRealParam(origscip, "limits/time", &timelimit) );
2477 if ( sepadata->timelimit < timelimit )
2478 timelimit = sepadata->timelimit;
2479
2480 if ( ! SCIPisInfinity(origscip, timelimit) )
2481 {
2482 timelimit -= SCIPgetSolvingTime(origscip);
2483 if ( timelimit > 0.0 )
2484 {
2485 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
2486 }
2487 else
2488 {
2489 SCIPdebugMsg(origscip, "Reached timelimit.\n");
2490 *success = FALSE;
2491 return SCIP_OKAY;
2492 }
2493 }
2494
2495 /* determine memory limit */
2496 SCIP_CALL( SCIPgetRealParam(origscip, "limits/memory", &memorylimit) );
2497 if ( sepadata->memorylimit < memorylimit )
2498 memorylimit = sepadata->memorylimit;
2499
2500 if ( ! SCIPisInfinity(origscip, memorylimit) )
2501 {
2502 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
2503 memorylimit -= SCIPgetMemUsed(origscip)/1048576.0;
2504 memorylimit -= SCIPgetMemExternEstim(origscip)/1048576.0;
2505 if ( memorylimit > 0.0 )
2506 {
2507 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
2508 }
2509 else
2510 {
2511 SCIPdebugMsg(origscip, "Reached memorylimit.\n");
2512 *success = TRUE;
2513 return SCIP_OKAY;
2514 }
2515 }
2516
2517 /* set node limit for subproblem */
2518 if ( sepadata->minnodelimit < 0 || sepadata->maxnodelimit < 0 )
2519 nodelimit = SCIP_LONGINT_MAX;
2520 else
2521 {
2522 assert( sepadata->minnodelimit >= 0 && sepadata->maxnodelimit >= 0 );
2523 nodelimit = SCIPgetNLPIterations(origscip);
2524 nodelimit = MAX(sepadata->minnodelimit, nodelimit);
2525 nodelimit = MIN(sepadata->maxnodelimit, nodelimit);
2526 }
2527 assert( nodelimit >= 0 );
2528 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
2529
2530 /* try to create primal solutions of CG-MIP problem via tableau cuts */
2531 if ( sepadata->genprimalsols )
2532 {
2533 SCIP_CALL( SCIPtransformProb(subscip) );
2534 SCIP_CALL( createCGMIPprimalsols(origscip, sepadata, mipdata) );
2535 }
2536
2537 SCIPdebugMsg(origscip, "Solving sub-SCIP (time limit: %f mem limit: %f node limit: %" SCIP_LONGINT_FORMAT ") ...\n", timelimit, memorylimit, nodelimit);
2538
2539 /* disable statistic timing inside sub SCIP */
2540 if ( ! sepadata->output )
2541 {
2542 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
2543 }
2544
2545 /* check whether we want a complete solve */
2546 if ( ! sepadata->earlyterm )
2547 {
2548 retcode = SCIPsolve(subscip);
2549 SCIPdebugMsg(origscip, "Finished solving CG-MIP (dualbound: %g, solving time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ", nodelimit: %" SCIP_LONGINT_FORMAT").\n",
2550 SCIPgetDualbound(subscip), SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), nodelimit);
2551
2552 /* errors in solving the subproblem should not kill the overall solving process;
2553 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
2554 if ( retcode != SCIP_OKAY )
2555 {
2556#ifndef NDEBUG
2557 SCIP_CALL( retcode );
2558#endif
2559 SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2560 *success = FALSE;
2561 return SCIP_OKAY;
2562 }
2563
2564 status = SCIPgetStatus(subscip);
2565
2566#ifdef SCIP_OUTPUT
2567 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2568#else
2569 if ( sepadata->output )
2570 {
2571 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2572 }
2573#endif
2574
2575 /* if the problem is infeasible (can happen because of violation constraint) */
2576 if ( status == SCIP_STATUS_INFEASIBLE || status == SCIP_STATUS_INFORUNBD )
2577 {
2578 SCIPdebugMsg(origscip, "CG-MIP separation problem infeasible.\n");
2579 *success = FALSE;
2580 return SCIP_OKAY;
2581 }
2582
2583 /* if the solution ran into the time limit */
2584 if ( status == SCIP_STATUS_TIMELIMIT )
2585 {
2586 SCIPdebugMsg(origscip, "CG-MIP separation problem ran into time limit.\n");
2587 *success = FALSE;
2588 return SCIP_OKAY;
2589 }
2590
2591 /* if the solution process was terminated */
2592 if ( status == SCIP_STATUS_USERINTERRUPT )
2593 {
2594 SCIPdebugMsg(origscip, "CG-MIP separation problem stopped by user interrupt.\n");
2595 *success = FALSE;
2596 return SCIP_OKAY;
2597 }
2598
2599 /* all other statuses except optimal or node limit are invalid */
2600 if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_NODELIMIT )
2601 {
2602 SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2603 return SCIP_ERROR;
2604 }
2605 }
2606 else
2607 {
2608 /* otherwise we want a heuristic solve */
2609
2610 /* -> solve until first solution is found */
2611 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", 1) );
2612 retcode = SCIPsolve(subscip);
2613 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", -1) );
2614
2615 /* errors in solving the subproblem should not kill the overall solving process;
2616 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
2617 if ( retcode != SCIP_OKAY )
2618 {
2619#ifndef NDEBUG
2620 SCIP_CALL( retcode );
2621#endif
2622 SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2623 *success = FALSE;
2624 return SCIP_OKAY;
2625 }
2626
2627 status = SCIPgetStatus(subscip);
2628
2629 /* if the solution process was terminated or the problem is infeasible (can happen because of violation constraint) */
2630 if ( status == SCIP_STATUS_TIMELIMIT || status == SCIP_STATUS_USERINTERRUPT || status == SCIP_STATUS_NODELIMIT ||
2631 status == SCIP_STATUS_INFEASIBLE || status == SCIP_STATUS_INFORUNBD || status == SCIP_STATUS_MEMLIMIT )
2632 {
2633 /* output statistics before stopping */
2634#ifdef SCIP_OUTPUT
2635 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2636#else
2637 if ( sepadata->output )
2638 {
2639 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2640 }
2641#endif
2642 *success = FALSE;
2643 return SCIP_OKAY;
2644 }
2645
2646 /* all other statuses except optimal or bestsollimit are invalid - (problem cannot be infeasible) */
2647 if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_BESTSOLLIMIT )
2648 {
2649 SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2650 return SCIP_ERROR;
2651 }
2652
2653 /* solve some more, if a feasible solution was found */
2654 if ( status == SCIP_STATUS_BESTSOLLIMIT )
2655 {
2656 SCIPdebugMsg(origscip, "Continue solving separation problem (current time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ") ...\n",
2657 SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip));
2658
2659 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", STALLNODELIMIT) );
2660 retcode = SCIPsolve(subscip);
2661 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", -1LL) );
2662
2663 SCIPdebugMsg(origscip, "Finished solving CG-MIP (dualbound: %g, solving time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ", nodelimit: %" SCIP_LONGINT_FORMAT").\n",
2664 SCIPgetDualbound(subscip), SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), nodelimit);
2665
2666 /* errors in solving the subproblem should not kill the overall solving process;
2667 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
2668 if ( retcode != SCIP_OKAY )
2669 {
2670#ifndef NDEBUG
2671 SCIP_CALL( retcode );
2672#endif
2673 SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2674 *success = FALSE;
2675 return SCIP_OKAY;
2676 }
2677
2678 status = SCIPgetStatus(subscip);
2679 assert( status != SCIP_STATUS_BESTSOLLIMIT );
2680
2681#ifdef SCIP_OUTPUT
2682 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2683#else
2684 if ( sepadata->output )
2685 {
2686 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2687 }
2688#endif
2689
2690 /* if the solution process was terminated */
2691 if ( status == SCIP_STATUS_TIMELIMIT || status == SCIP_STATUS_USERINTERRUPT || status == SCIP_STATUS_MEMLIMIT )
2692 {
2693 *success = FALSE;
2694 return SCIP_OKAY;
2695 }
2696
2697 /* all other statuses except optimal or bestsollimit are invalid */
2698 if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_STALLNODELIMIT && status != SCIP_STATUS_NODELIMIT )
2699 {
2700 SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2701 return SCIP_ERROR;
2702 }
2703 }
2704 }
2705
2706 return SCIP_OKAY;
2707}
2708
2709/** Computes cut from the given multipliers
2710 *
2711 * When computing the cut, we take the fractional part of the multipliers. This is known to produce stronger cuts in
2712 * the pure integer case, since the cut is the sum of the one using fractional parts and integer multiples of the
2713 * original constraints. However, if there are continuous variables, the resulting cut might not be valid. This is
2714 * checked and returned.
2715 *
2716 * Moreover, the cut computed here in general will not be the same as the one computed with the
2717 * sub-MIP, because of numerical differences. Here, we only combine rows whose corresponding
2718 * multiplier is positive w.r.t. the feasibility tolerance. In the sub-MIP, however, the rows are
2719 * combined in any case. This makes a difference, if the coefficients in the matrix are large and
2720 * hence yield a value that is larger than the tolerance.
2721 *
2722 * Because of the transformations we have the following:
2723 *
2724 * If variable \f$x_j\f$ was complemented, we have \f$x'_j = u_j - x_j\f$. If in the transformed
2725 * system the lower bound is used, its corresponding multiplier is \f$y^T A'_j - \lfloor y^T A'_j
2726 * \rfloor\f$, which corresponds to
2727 * \f[
2728 * y^T A'_j - \lfloor y^T A'_j \rfloor = - y^T A_j - \lfloor - y^T A_j \rfloor = - y^T A_j + \lceil y^T A_j \rceil
2729 * \f]
2730 * in the original system.
2731 *
2732 * If such a variable was at its upper bound before the transformation, it is at its lower bound
2733 * afterwards. Hence, its contribution to the cut is 0.
2734 *
2735 * Note that if the original LP-solution does not satisfy some of the rows with equality, the
2736 * violation of the cut might be smaller than what is computed with the reduced sub-MIP.
2737 *
2738 * Furthermore, note that if continuous variables have been shifted, the computed violation may be
2739 * different as well, because the necessary changes in the lhs/rhs are not used here anymore.
2740 *
2741 * @todo Check if cut is correct if continuous variables have been shifted.
2742 */
2743static
2744SCIP_RETCODE computeCut(
2745 SCIP* scip, /**< original scip */
2746 SCIP_SEPA* sepa, /**< separator */
2747 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
2748 SCIP_SEPADATA* sepadata, /**< separator data */
2749 SCIP_SOL* sol, /**< current solution for sub-MIP */
2750 SCIP_Bool usefrac, /**< use fractional value of multipliers */
2751 SCIP_Real* cutcoefs, /**< coefficients of the cut */
2752 SCIP_Real* cutrhs, /**< rhs of the cut */
2753 SCIP_Bool* localrowsused, /**< pointer to store whether local rows were used in summation */
2754 SCIP_Bool* localboundsused, /**< pointer to store whether local bounds were used in summation */
2755 int* cutrank, /**< pointer to store the cut rank */
2756 SCIP_Bool* success /**< whether we produced a valid cut */
2757 )
2758{
2759 SCIP* subscip;
2760 SCIP_VAR** vars;
2761 SCIP_ROW** rows;
2762 SCIP_COL** cols;
2763 SCIP_Real val;
2764 SCIP_Real maxabsweight;
2765 int nvars;
2766 int ncols;
2767 int nrows;
2768 int i;
2769 int j;
2770
2771 assert( scip != NULL );
2772 assert( mipdata != NULL );
2773 assert( sepadata != NULL );
2774 assert( cutcoefs != NULL );
2775 assert( cutrhs != NULL );
2776 assert( localrowsused != NULL );
2777 assert( localboundsused != NULL );
2778 assert( cutrank != NULL );
2779 assert( success != NULL );
2780
2781 /* initialize */
2782 *localrowsused = FALSE;
2783 *localboundsused = FALSE;
2784 *cutrank = 0;
2785 *success = TRUE;
2786
2787 subscip = mipdata->subscip;
2788 assert( subscip != NULL );
2789
2790 /* get data */
2791 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2792 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
2793 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
2794 assert( nrows == (int) mipdata->nrows );
2795 assert( ncols == (int) mipdata->ncols );
2796
2797 BMSclearMemoryArray(cutcoefs, nvars);
2798 *cutrhs = 0.0;
2799
2800 /* find maximal absolute weight */
2801 maxabsweight = 0.0;
2802 for (i = 0; i < nrows; ++i)
2803 {
2804 SCIP_ROW* row;
2805 SCIP_Real absweight = 0.0;
2806
2807 row = rows[i];
2808 assert( row != NULL );
2809
2810 /* skip modifiable rows and local rows, unless allowed */
2811 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
2812 {
2813 assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL );
2814 continue;
2815 }
2816
2817 /* get weight from solution (take larger of the values of lhs/rhs) */
2818 if ( mipdata->ylhs[i] != NULL )
2819 {
2820 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[i]);
2821
2822 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2823 if ( usefrac )
2824 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2825
2826 if ( SCIPisFeasPositive(scip, val) )
2827 absweight = val;
2828
2829 assert( ! sepadata->onlyrankone || SCIProwGetOriginSepa(row) != sepa );
2830 }
2831 if ( mipdata->yrhs[i] != NULL )
2832 {
2833 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[i]);
2834
2835 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2836 if ( usefrac )
2837 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2838
2839 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
2840 if ( SCIPisFeasGT(scip, val, absweight) )
2841 absweight = val;
2842
2843 assert( ! sepadata->onlyrankone || SCIProwGetOriginSepa(row) != sepa );
2844 }
2845 assert( ! SCIPisNegative(scip, absweight) );
2846
2847 if ( absweight > maxabsweight )
2848 maxabsweight = absweight;
2849 }
2850
2851 /* get weight from objective cuts */
2852 if ( sepadata->useobjub || sepadata->useobjlb )
2853 {
2854 SCIP_Real absweight = 0.0;
2855
2856 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
2857
2858 if ( mipdata->ylhs[mipdata->nrows] != NULL )
2859 {
2860 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]);
2861 if ( usefrac )
2862 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2863
2864 if ( SCIPisFeasPositive(scip, val) )
2865 absweight = val;
2866 }
2867 if ( mipdata->yrhs[mipdata->nrows] != NULL )
2868 {
2869 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]);
2870 if ( usefrac )
2871 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2872
2873 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
2874 if ( SCIPisFeasGT(scip, val, absweight) )
2875 absweight = val;
2876 }
2877
2878 if ( absweight > maxabsweight )
2879 maxabsweight = absweight;
2880 }
2881
2882 /* calculate the row summation */
2883 for (i = 0; i < nrows; ++i)
2884 {
2885 SCIP_ROW* row;
2886 SCIP_Real weight;
2887 SCIP_Real absweight;
2888 SCIP_Bool uselhs;
2889
2890 row = rows[i];
2891 assert( row != NULL );
2892
2893 /* skip modifiable rows and local rows, unless allowed */
2894 if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && ! sepadata->allowlocal) )
2895 {
2896 assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL );
2897 continue;
2898 }
2899
2900 /* get weight from solution */
2901 weight = 0.0;
2902 uselhs = FALSE;
2903 if ( mipdata->ylhs[i] != NULL )
2904 {
2905 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[i]);
2906 assert( ! SCIPisFeasNegative(subscip, val) );
2907
2908 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2909 if ( usefrac )
2910 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2911
2912 if ( SCIPisFeasPositive(scip, val) )
2913 {
2914 uselhs = TRUE;
2915 weight = -val;
2916 }
2917 }
2918 if ( mipdata->yrhs[i] != NULL )
2919 {
2920 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[i]);
2921 assert( ! SCIPisFeasNegative(subscip, val) );
2922
2923 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2924 if ( usefrac )
2925 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2926
2927 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
2928 if ( SCIPisFeasGT(scip, val, REALABS(weight)) )
2929 {
2930 uselhs = FALSE;
2931 weight = val;
2932 }
2933 }
2934
2935 /* add row if weight is nonzero and lies within range */
2936 absweight = REALABS(weight);
2937 if ( ! SCIPisSumZero(scip, weight) && absweight * MAXWEIGHTRANGE >= maxabsweight )
2938 {
2939 SCIP_COL** rowcols;
2940 SCIP_Real* rowvals;
2941
2942 rowcols = SCIProwGetCols(row);
2943 rowvals = SCIProwGetVals(row);
2944
2945 /* add the row coefficients to the sum */
2946 for (j = 0; j < SCIProwGetNLPNonz(row); ++j)
2947 {
2948 SCIP_VAR* var;
2949 int idx;
2950
2951 assert( rowcols[j] != NULL );
2952 var = SCIPcolGetVar(rowcols[j]);
2953
2954 assert( var != NULL );
2955 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
2956 assert( SCIPvarGetCol(var) == rowcols[j] );
2957
2958 idx = SCIPvarGetProbindex(var);
2959 assert( 0 <= idx && idx < nvars );
2960
2961 cutcoefs[idx] += weight * rowvals[j];
2962 }
2963
2964 /* compute rhs */
2965 if ( uselhs )
2966 {
2967 assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
2968 val = SCIProwGetLhs(row) - SCIProwGetConstant(row);
2969 if ( SCIProwIsIntegral(row) )
2970 val = SCIPfeasCeil(scip, val); /* row is integral: round left hand side up */
2971 }
2972 else
2973 {
2974 assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) );
2975 val = SCIProwGetRhs(row) - SCIProwGetConstant(row);
2976 if ( SCIProwIsIntegral(row) )
2977 val = SCIPfeasFloor(scip, val); /* row is integral: round right hand side down */
2978 }
2979 *cutrhs += weight * val;
2980
2981 *localrowsused = *localrowsused || SCIProwIsLocal(row);
2982
2983 if ( SCIProwGetRank(row) > *cutrank )
2984 *cutrank = SCIProwGetRank(row);
2985 }
2986 }
2987 /* add 1 to cutrank */
2988 ++(*cutrank);
2989
2990 /* get weight from objective bounds */
2991 if ( sepadata->useobjub || sepadata->useobjlb )
2992 {
2993 SCIP_Real weight = 0.0;
2994 SCIP_Bool uselhs = FALSE;
2995 SCIP_Real absweight;
2996
2997 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
2998
2999 if ( mipdata->ylhs[mipdata->nrows] != NULL )
3000 {
3001 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]);
3002 assert( ! SCIPisFeasNegative(subscip, val) );
3003 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3004 if ( usefrac )
3005 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3006
3007 if ( SCIPisFeasPositive(scip, val) )
3008 {
3009 uselhs = TRUE;
3010 weight = -val;
3011 }
3012 }
3013 if ( mipdata->yrhs[mipdata->nrows] != NULL )
3014 {
3015 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]);
3016 assert( ! SCIPisFeasNegative(subscip, val) );
3017 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3018 if ( usefrac )
3019 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3020
3021 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
3022 if ( SCIPisFeasGT(scip, val, REALABS(weight)) )
3023 {
3024 uselhs = FALSE;
3025 weight = val;
3026 }
3027 }
3028
3029 /* add objective row if weight is nonzero and lies within range */
3030 absweight = REALABS(weight);
3031 if ( ! SCIPisSumZero(scip, weight) && absweight * MAXWEIGHTRANGE >= maxabsweight )
3032 {
3033 SCIP_Real obj;
3034 int idx;
3035
3036 /* add the objective row coefficients to the sum */
3037 for (j = 0; j < ncols; ++j)
3038 {
3039 assert( cols[j] != NULL );
3040
3041 obj = SCIPcolGetObj(cols[j]);
3042 if ( ! SCIPisZero(scip, obj) )
3043 {
3044 idx = SCIPvarGetProbindex( SCIPcolGetVar(cols[j]) );
3045 assert( 0 <= idx && idx < nvars );
3046 cutcoefs[idx] += weight * obj;
3047 }
3048 }
3049
3050 /* compute rhs */
3051 if ( uselhs )
3052 {
3053 val = SCIPgetLowerbound(scip);
3054 assert( ! SCIPisInfinity(scip, -val) );
3055 if ( SCIPisObjIntegral(scip) )
3056 val = SCIPfeasCeil(scip, val); /* objective is integral: round left hand side up */
3057 }
3058 else
3059 {
3060 val = SCIPgetUpperbound(scip);
3061 assert( ! SCIPisInfinity(scip, val) );
3062 if ( SCIPisObjIntegral(scip) )
3063 val = SCIPfeasFloor(scip, val); /* objective is integral: round right hand side down */
3064 }
3065 *cutrhs += weight * val;
3066 }
3067 }
3068
3069 /* add upper bounds */
3070 for (j = 0; j < ncols; ++j)
3071 {
3072 assert( cols[j] != NULL );
3073 if ( mipdata->z[j] != NULL )
3074 {
3075 assert( mipdata->coltype[j] == colPresent );
3076
3077 val = SCIPgetSolVal(subscip, sol, mipdata->z[j]);
3078 assert( ! SCIPisFeasNegative(subscip, val) );
3079
3080 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3081 if ( usefrac )
3082 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3083
3084 /* if a bound has been used */
3085 if ( SCIPisSumPositive(subscip, val) )
3086 {
3087 SCIP_VAR* var;
3088 int idx;
3089
3090 var = SCIPcolGetVar(cols[j]);
3091
3092 assert( var != NULL );
3093 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
3094 assert( SCIPvarIsIntegral(var) );
3095 assert( SCIPvarGetCol(var) == cols[j] );
3096
3097 idx = SCIPvarGetProbindex(var);
3098 assert( 0 <= idx && idx < nvars );
3099
3100 /* check whether variable is complemented */
3101 if ( mipdata->iscomplemented[j] )
3102 {
3103 SCIP_Real lbnd;
3104 lbnd = SCIPvarGetLbGlobal(var);
3105 assert( ! SCIPisInfinity(scip, -lbnd) );
3106 assert( SCIPisIntegral(scip, lbnd) );
3107 assert( SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPcolGetLb(cols[j])) );
3108
3109 /* variable should not be free */
3110 assert( ! SCIPisInfinity(scip, -lbnd) || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) );
3111
3112 /* if allowed, try to use stronger local bound */
3113 if ( sepadata->allowlocal && SCIPvarGetLbLocal(var) - 0.5 > lbnd )
3114 {
3115 lbnd = SCIPvarGetLbLocal(var);
3116 assert( SCIPisIntegral(scip, lbnd) );
3117 *localboundsused = TRUE;
3118 }
3119
3120 cutcoefs[idx] -= val;
3121 *cutrhs -= lbnd * val;
3122 }
3123 else
3124 {
3125 SCIP_Real ubnd;
3126 ubnd = SCIPvarGetUbGlobal(var);
3127 assert( ! SCIPisInfinity(scip, ubnd) );
3128 assert( SCIPisIntegral(scip, ubnd) );
3129 assert( SCIPisEQ(scip, SCIPvarGetUbLocal(var), SCIPcolGetUb(cols[j])) );
3130
3131 /* if allowed, try to use stronger local bound */
3132 if ( sepadata->allowlocal && SCIPvarGetUbLocal(var) + 0.5 < ubnd )
3133 {
3134 ubnd = SCIPvarGetUbLocal(var);
3135 assert( SCIPisIntegral(scip, ubnd) );
3136 *localboundsused = TRUE;
3137 }
3138
3139 cutcoefs[idx] += val;
3140 *cutrhs += ubnd * val;
3141 }
3142 }
3143 }
3144 }
3145
3146 /* check lower bounds for integral variables */
3147 for (j = 0; j < nvars; ++j)
3148 {
3149 SCIP_VAR* var;
3150 int pos;
3151
3152 var = vars[j];
3153 assert( var != NULL );
3154 pos = SCIPcolGetLPPos(SCIPvarGetCol(var));
3155
3156 /* a variable may have status COLUMN, but the corresponding column may not (yet) be in the LP */
3157 if ( pos >= 0 && mipdata->coltype[pos] != colContinuous && mipdata->coltype[pos] != colConverted )
3158 {
3159 assert( pos < ncols );
3160 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
3161 assert( SCIPvarIsIntegral(var) );
3162
3163 /* check whether variable is complemented */
3164 if ( mipdata->iscomplemented[pos] )
3165 {
3166 assert( ! mipdata->isshifted[pos] );
3167 /* if the variable is complemented, the multiplier for the upper bound arises from the
3168 lower bound multiplier for the transformed problem - because of the minus-sign in the
3169 transformation this yields a round-up operation. */
3170 val = SCIPfeasCeil(scip, cutcoefs[j]) - cutcoefs[j];
3171 assert( ! SCIPisFeasNegative(scip, val) );
3172
3173 /* only if variable needs to be rounded */
3174 if ( SCIPisSumPositive(scip, val) )
3175 {
3176 SCIP_Real ubnd;
3177 ubnd = SCIPvarGetUbGlobal(var);
3178 assert( ! SCIPisInfinity(scip, ubnd) );
3179 assert( SCIPisIntegral(scip, ubnd) );
3180
3181 /* variable should not be free */
3182 assert( ! SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) || ! SCIPisInfinity(scip, ubnd) );
3183
3184 /* if allowed, try to use stronger local bound */
3185 if ( sepadata->allowlocal && SCIPvarGetUbLocal(var) + 0.5 < ubnd )
3186 {
3187 ubnd = SCIPvarGetUbLocal(var);
3188 assert( SCIPisIntegral(scip, ubnd) );
3189 *localboundsused = TRUE;
3190 }
3191
3192 /* round cut coefficients, i.e., add val to cutcoefs[j] */
3193 cutcoefs[j] = SCIPfeasCeil(scip, cutcoefs[j]);
3194
3195 /* correct rhs */
3196 if ( ! SCIPisSumZero(scip, ubnd) )
3197 *cutrhs += ubnd * val;
3198 }
3199 }
3200 else
3201 {
3202 /* compute multiplier for lower bound: */
3203 val = cutcoefs[j] - SCIPfeasFloor(scip, cutcoefs[j]);
3204 assert( ! SCIPisFeasNegative(scip, val) );
3205
3206 /* only if variable needs to be rounded */
3207 if ( SCIPisSumPositive(scip, val) )
3208 {
3209 SCIP_Real lbnd;
3210 lbnd = SCIPvarGetLbGlobal(var);
3211 assert( ! SCIPisInfinity(scip, -lbnd) );
3212 assert( SCIPisIntegral(scip, lbnd) );
3213
3214 /* variable should not be free */
3215 assert( ! SCIPisInfinity(scip, -lbnd) || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) );
3216
3217 /* if allowed, try to use stronger local bound */
3218 if ( sepadata->allowlocal && SCIPvarGetLbLocal(var) - 0.5 > lbnd )
3219 {
3220 lbnd = SCIPvarGetLbLocal(var);
3221 assert( SCIPisIntegral(scip, lbnd) );
3222 *localboundsused = TRUE;
3223 }
3224
3225 /* round cut coefficients, i.e., subtract val from cutcoefs[j] */
3226 cutcoefs[j] = SCIPfeasFloor(scip, cutcoefs[j]);
3227
3228 /* correct rhs */
3229 if ( ! SCIPisSumZero(scip, lbnd) )
3230 *cutrhs -= lbnd * val;
3231 }
3232 }
3233 }
3234 else
3235 {
3236 /* force coefficients of all continuous variables or of variables not in the lp to zero */
3237 assert( pos == -1 || mipdata->coltype[pos] == colContinuous || mipdata->coltype[pos] == colConverted );
3238
3239 /* check whether all coefficients for continuous or converted variables are nonnegative */
3240 if ( pos >= 0 )
3241 {
3242 if ( SCIPisFeasNegative(scip, cutcoefs[j]) )
3243 {
3244 *success = FALSE;
3245 break;
3246 }
3247 }
3248
3249 cutcoefs[j] = 0.0;
3250 }
3251 }
3252
3253 /* round rhs */
3254 *cutrhs = SCIPfeasFloor(scip, *cutrhs);
3255
3256 return SCIP_OKAY;
3257}
3258
3259/** Create CG-cut directly from solution of sub-MIP */
3260static
3261SCIP_RETCODE createCGCutDirect(
3262 SCIP* scip, /**< SCIP data structure */
3263 SCIP_SEPA* sepa, /**< separator */
3264 SCIP_SEPADATA* sepadata, /**< separator data */
3265 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
3266 SCIP_SOL* sol, /**< solution of sub-MIP */
3267 SCIP_Real* cutcoefs, /**< cut coefficients */
3268 int* cutinds, /**< problem indices of variables appearing in cut */
3269 SCIP_Real* cutvals, /**< values of variables in cut */
3270 SCIP_Real* varsolvals, /**< solution value of variables */
3271 SCIP_Real* weights, /**< weights to compute cmir cut */
3272 int* nprevrows, /**< number of previously generated rows */
3273 SCIP_ROW** prevrows, /**< previously generated rows */
3274 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
3275 unsigned int* ngen /**< number of generated cuts */
3276 )
3277{
3278 char name[SCIP_MAXSTRLEN];
3279 SCIP_Bool cutislocal;
3280 SCIP_Bool localrowsused;
3281 SCIP_Bool localboundsused;
3282 SCIP_Real cutrhs;
3283 SCIP_Real cutact;
3284 SCIP_Bool success;
3285 SCIP_VAR** vars;
3286 int cutrank = 0;
3287 int nvars;
3288 int k;
3289
3290 assert( scip != NULL );
3291 assert( sepadata != NULL );
3292 assert( mipdata != NULL );
3293 assert( sol != NULL );
3294 assert( cutcoefs != NULL );
3295 assert( cutinds != NULL );
3296 assert( cutvals != NULL );
3297 assert( varsolvals != NULL );
3298 assert( weights != NULL );
3299 assert( nprevrows != NULL );
3300 assert( prevrows != NULL );
3301 assert( cutoff != NULL );
3302 assert( ngen != NULL );
3303
3304 /* get variable data */
3305 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3306
3307 cutrhs = 0.0;
3308 localrowsused = FALSE;
3309 localboundsused = FALSE;
3310 *cutoff = FALSE;
3311 success = TRUE;
3312
3313 /* compute coefficients */
3314 SCIP_CALL( computeCut(scip, sepa, mipdata, sepadata, sol, TRUE, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) );
3315 cutislocal = localrowsused || localboundsused;
3316
3317 /* Take next solution if cut was not valid - this can easily happen for mixed-integer problems, see function computeCut(). */
3318 if ( ! success )
3319 {
3320 /* try again without using fractional value */
3321 SCIP_CALL( computeCut(scip, sepa, mipdata, sepadata, sol, FALSE, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) );
3322 cutislocal = localrowsused || localboundsused;
3323
3324 if ( ! success )
3325 {
3326 SCIPdebugMsg(scip, "cut not valid - skipping ...\n");
3327 return SCIP_OKAY;
3328 }
3329 }
3330
3331 /* compute activity */
3332 cutact = 0.0;
3333 for (k = 0; k < nvars; ++k)
3334 cutact += cutcoefs[k] * varsolvals[k];
3335
3336#ifdef SCIP_DISABLED_CODE
3337 /* the following test should be treated with care because of numerical differences - see computeCut() */
3338 {
3339 /* check for correctness of computed values */
3340 SCIP* subscip;
3341 SCIP_Real obj = 0.0;
3342 SCIP_Real val;
3343 SCIP_Bool contVarShifted = FALSE;
3344 unsigned int j;
3345 SCIP_COL** cols;
3346 int ncols;
3347
3348 subscip = mipdata->subscip;
3349 assert( subscip != NULL );
3350
3351 SCIP_CALL( SCIPprintSol(subscip, sol, NULL, FALSE) );
3352
3353 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
3354 for (j = 0; j < mipdata->ncols; ++j)
3355 {
3356 if ( mipdata->coltype[j] == colPresent )
3357 {
3358 int idx;
3359 assert( mipdata->alpha[j] != NULL );
3360 val = SCIPgetSolVal(subscip, sol, mipdata->alpha[j]);
3361 assert( SCIPisFeasIntegral(subscip, val) );
3362 idx = SCIPvarGetProbindex(SCIPcolGetVar(cols[j]));
3363 assert( SCIPisFeasEQ(scip, val, cutcoefs[idx]) );
3364 obj += val * SCIPvarGetObj(mipdata->alpha[j]);
3365 }
3366 else
3367 {
3368 if ( (mipdata->coltype[j] == colContinuous || mipdata->coltype[j] == colConverted) && mipdata->isshifted[j] )
3369 contVarShifted = TRUE;
3370 }
3371 }
3372 assert( mipdata->beta != NULL );
3373 val = SCIPgetSolVal(subscip, sol, mipdata->beta);
3374 assert( SCIPisFeasIntegral(subscip, val) );
3375 obj += val * SCIPvarGetObj(mipdata->beta);
3376 assert( contVarShifted || SCIPisFeasEQ(scip, obj, cutact - cutrhs) );
3377 }
3378#endif
3379
3380 /* if successful, convert dense cut into sparse row, and add the row as a cut */
3381 if ( SCIPisFeasGT(scip, cutact, cutrhs) )
3382 {
3383 SCIP_Real cutnorm;
3384 int cutlen;
3385
3386 /* store the cut as sparse row, calculate activity and norm of cut */
3387 SCIP_CALL( storeCutInArrays(scip, nvars, cutcoefs, varsolvals, mipdata->normtype,
3388 cutinds, cutvals, &cutlen, &cutact, &cutnorm) );
3389
3390 SCIPdebugMsg(scip, "act=%f, rhs=%f, norm=%f, eff=%f\n", cutact, cutrhs, cutnorm, (cutact - cutrhs)/cutnorm);
3391
3392 /* if norm is 0, the cut is trivial */
3393 if ( SCIPisPositive(scip, cutnorm) )
3394 {
3395 SCIP_Bool violated = SCIPisEfficacious(scip, (cutact - cutrhs)/cutnorm);
3396
3397 if ( violated || (sepadata->usecutpool && ! cutislocal ) )
3398 {
3399 SCIP_ROW* cut;
3400
3401 /* create the cut */
3402 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
3403 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
3404 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
3405
3406 for (k = 0; k < cutlen; ++k)
3407 {
3408 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutvals[k]) );
3409 }
3410
3411 /* set cut rank */
3412 SCIProwChgRank(cut, cutrank);
3413
3414 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
3415
3416 /*SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) );*/
3417
3418 /* add cut to pool */
3419 if ( ! cutislocal )
3420 {
3421 assert( violated || sepadata->usecutpool );
3422 SCIP_CALL( SCIPaddPoolCut(scip, cut) );
3423 }
3424
3425 /* add cut if it is violated */
3426 if ( violated )
3427 {
3428 /* check whether cut has been found before - may happened due to projection */
3429 for (k = 0; k < *nprevrows; ++k)
3430 {
3431 SCIP_Real parval;
3432
3433 assert( prevrows[k] != NULL );
3434 parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
3435 /* exit if row is parallel to existing cut and rhs is not better */
3436 if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
3437 break;
3438 }
3439
3440 /* if cut is new */
3441 if ( k >= *nprevrows )
3442 {
3443 prevrows[*nprevrows] = cut;
3444 ++(*nprevrows);
3445
3446 SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
3447 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3448 SCIPgetCutEfficacy(scip, NULL, cut),
3449 SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
3450 SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
3451#ifdef SCIP_DEBUG
3452 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3453#else
3454 if ( sepadata->output )
3455 {
3456 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3457 }
3458#endif
3459 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
3460 ++(*ngen);
3461 }
3462 else
3463 {
3464 SCIPdebugMsg(scip, "Cut already exists.\n");
3465 /* release the row */
3466 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3467 }
3468 }
3469 else
3470 {
3471 /* release the row */
3472 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3473 }
3474 }
3475 }
3476 }
3477
3478 return SCIP_OKAY;
3479}
3480
3481
3482/** create CG-cut via CMIR-function */
3483static
3484SCIP_RETCODE createCGCutCMIR(
3485 SCIP* scip, /**< SCIP data structure */
3486 SCIP_SEPA* sepa, /**< separator */
3487 SCIP_SEPADATA* sepadata, /**< separator data */
3488 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
3489 SCIP_SOL* sol, /**< solution of sub-MIP */
3490 SCIP_AGGRROW* aggrrow, /**< aggregation row to use for creating MIR cut */
3491 SCIP_Real* cutcoefs, /**< cut coefficients */
3492 int* cutinds, /**< problem indices of variables appearing in cut */
3493 SCIP_Real* cutvals, /**< values of variables in cut */
3494 SCIP_Real* varsolvals, /**< solution value of variables */
3495 SCIP_Real* weights, /**< weights to compute cmir cut */
3496 int* boundsfortrans, /**< bounds for cmir function of NULL */
3497 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds for cmir function or NULL */
3498 int* nprevrows, /**< number of previously generated rows */
3499 SCIP_ROW** prevrows, /**< previously generated rows */
3500 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
3501 unsigned int* ngen /**< number of generated cuts */
3502 )
3503{
3504 char name[SCIP_MAXSTRLEN];
3505 SCIP_Longint maxdnom;
3506 SCIP_Bool cutislocal;
3507 SCIP_Real maxscale;
3508 SCIP_Real cutrhs;
3509 SCIP_Real cutefficacy;
3510 SCIP_Bool success;
3511 SCIP_ROW** rows;
3512 SCIP_VAR** vars;
3513 SCIP* subscip;
3514 int nrows;
3515 int nvars;
3516 int k;
3517 int cutrank;
3518 int cutnnz;
3519
3520 assert( scip != NULL );
3521 assert( sepadata != NULL );
3522 assert( mipdata != NULL );
3523 assert( sol != NULL );
3524 assert( cutcoefs != NULL );
3525 assert( cutinds != NULL );
3526 assert( cutvals != NULL );
3527 assert( varsolvals != NULL );
3528 assert( weights != NULL );
3529 assert( nprevrows != NULL );
3530 assert( prevrows != NULL );
3531 assert( cutoff != NULL );
3532 assert( ngen != NULL );
3533
3534 *cutoff = FALSE;
3535 subscip = mipdata->subscip;
3536 assert( subscip != NULL );
3537
3538 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
3539 assert( nrows > 0 );
3540 assert( (int) mipdata->nrows == nrows );
3541
3542 /* @todo more advanced settings - compare sepa_gomory.c */
3543 maxdnom = (SCIP_Longint) sepadata->cutcoefbnd+1;
3544 maxscale = 10000.0;
3545
3546 /* get variable data */
3547 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3548
3549 /* generate weights */
3550 for (k = 0; k < nrows; ++k)
3551 {
3552 SCIP_Real val;
3553
3554 weights[k] = 0;
3555 if ( mipdata->ylhs[k] != NULL )
3556 {
3557 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3558
3559 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[k]);
3560 assert( ! SCIPisFeasNegative(subscip, val) );
3561
3562 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3563 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3564
3565 if ( SCIPisFeasPositive(subscip, val) )
3566 weights[k] = -val;
3567 }
3568
3569 if ( mipdata->yrhs[k] != NULL )
3570 {
3571 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3572
3573 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[k]);
3574 assert( ! SCIPisFeasNegative(subscip, val) );
3575
3576 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3577 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3578
3579 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
3580 if ( SCIPisFeasGT(scip, val, ABS(weights[k])) )
3581 weights[k] = val;
3582 }
3583 }
3584
3585 /* set up data for bounds to use */
3586 if ( sepadata->cmirownbounds )
3587 {
3588 int typefortrans;
3589
3590 assert( boundsfortrans != NULL );
3591 assert( boundtypesfortrans != NULL );
3592
3593 if ( sepadata->allowlocal )
3594 typefortrans = -2;
3595 else
3596 typefortrans = -1;
3597
3598 /* check all variables */
3599 for (k = 0; k < nvars; ++k)
3600 {
3601 int pos;
3602 SCIP_VAR* var;
3603
3604 var = vars[k];
3605 assert( var != NULL );
3606 pos = SCIPcolGetLPPos(SCIPvarGetCol(var));
3607
3608 if ( pos < 0 )
3609 continue;
3610
3611 assert( pos < (int) mipdata->ncols );
3612 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
3613
3614 boundsfortrans[k] = typefortrans;
3615 boundtypesfortrans[k] = SCIP_BOUNDTYPE_LOWER;
3616
3617 if ( mipdata->coltype[pos] == colContinuous || mipdata->coltype[pos] == colConverted )
3618 {
3619 assert( SCIPvarIsIntegral(var) || mipdata->coltype[pos] != colContinuous );
3620 continue;
3621 }
3622
3623 /* check upper bound */
3624 if ( mipdata->z[pos] != NULL && SCIPisSumPositive(subscip, SCIPgetSolVal(subscip, sol, mipdata->z[pos])) )
3625 {
3626 /* check whether variable is complemented */
3627 if ( ! mipdata->iscomplemented[pos] )
3628 boundtypesfortrans[k] = SCIP_BOUNDTYPE_UPPER;
3629 /* otherwise use lower bound */
3630 }
3631 else
3632 {
3633 /* check whether variable is complemented */
3634 if ( mipdata->iscomplemented[pos] )
3635 boundtypesfortrans[k] = SCIP_BOUNDTYPE_UPPER;
3636 /* otherwise use lower bound */
3637 }
3638 }
3639 }
3640
3641 /* create a MIR cut using the above calculated weights */
3642 cutefficacy = -1.0;
3643 cutrhs = -1.0;
3644 SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, weights, NULL, -1, FALSE,
3645 sepadata->allowlocal, 2, (int) MAXAGGRLEN(nvars), &success) );
3646
3647 if ( ! success )
3648 return SCIP_OKAY;
3649
3650 SCIP_CALL( SCIPcalcMIR(scip, NULL, POSTPROCESS, BOUNDSWITCH, VARTYPEUSEVBDS, sepadata->allowlocal, FIXINTEGRALRHS, boundsfortrans,
3651 boundtypesfortrans, MINFRAC, MAXFRAC, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy,
3652 &cutrank, &cutislocal, &success) );
3653
3654 assert( sepadata->allowlocal || !cutislocal );
3655 SCIPdebugMsg(scip, "CMIR: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success,
3656 SCIPisEfficacious(scip, cutefficacy) ? " " : " not ", cutefficacy, cutrhs);
3657
3658 /* If successful, convert dense cut into sparse row, and add the row as a cut only if the cut if violated - if it is
3659 * not violated we might store non-local cuts in the pool. */
3660 if ( success && (SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) )
3661 {
3662 SCIP_ROW* cut;
3663
3664 /* create the cut */
3665 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
3666 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
3667
3668 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
3669
3670 for (k = 0; k < cutnnz; ++k)
3671 {
3672 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutcoefs[k]) );
3673 }
3674
3675 assert( success );
3676
3677 /* set cut rank */
3678 SCIProwChgRank(cut, cutrank);
3679
3680#ifdef SCIP_DEBUG
3681 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3682#else
3683 if ( sepadata->output )
3684 {
3685 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3686 }
3687#endif
3688
3689 /* try to scale the cut to integral values */
3690 SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
3691 maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
3692
3693 /* if the cut could be made integral */
3694 if ( success )
3695 {
3696 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
3697
3698 /* add cut to pool */
3699 if ( ! cutislocal )
3700 {
3701 assert( SCIPisEfficacious(scip, cutefficacy) || sepadata->usecutpool );
3702 SCIP_CALL( SCIPaddPoolCut(scip, cut) );
3703 }
3704
3705 if ( ! SCIPisCutEfficacious(scip, NULL, cut) )
3706 {
3707 SCIPdebugMsg(scip, " -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
3708 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3709 SCIPgetCutEfficacy(scip, NULL, cut));
3710
3711 /* release the row */
3712 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3713 }
3714 else
3715 {
3716 /* check whether cut has been found before - may happend due to projection */
3717 for (k = 0; k < *nprevrows; ++k)
3718 {
3719 SCIP_Real parval;
3720
3721 assert( prevrows[k] != NULL );
3722 parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
3723 /* exit if row is parallel to existing cut and rhs is not better */
3724 if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
3725 break;
3726 }
3727
3728 /* if cut is new */
3729 if ( k >= *nprevrows )
3730 {
3731 prevrows[*nprevrows] = cut;
3732 ++(*nprevrows);
3733
3734 SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n",
3735 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3736 SCIPgetCutEfficacy(scip, NULL, cut), SCIProwGetRank(cut),
3737 SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
3738 SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
3739#ifdef SCIP_OUTPUT
3740 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3741#else
3742 if ( sepadata->output )
3743 {
3744 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3745 }
3746#endif
3747 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
3748 ++(*ngen);
3749 }
3750 else
3751 {
3752 SCIPdebugMsg(scip, "Cut already exists.\n");
3753 /* release the row */
3754 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3755 }
3756 }
3757 }
3758 else
3759 {
3760 SCIPdebugMsg(scip, " -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n",
3761 name, cutefficacy, cutrhs);
3762
3763 /* release the row */
3764 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3765 }
3766 }
3767
3768 return SCIP_OKAY;
3769}
3770
3771
3772/** create CG-cut via strong-CG-function */
3773static
3774SCIP_RETCODE createCGCutStrongCG(
3775 SCIP* scip, /**< SCIP data structure */
3776 SCIP_SEPA* sepa, /**< separator */
3777 SCIP_SEPADATA* sepadata, /**< separator data */
3778 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
3779 SCIP_SOL* sol, /**< solution of sub-MIP */
3780 SCIP_AGGRROW* aggrrow, /**< aggregation row to use for creating MIR cut */
3781 SCIP_Real* cutcoefs, /**< cut coefficients */
3782 int* cutinds, /**< problem indices of variables appearing in cut */
3783 SCIP_Real* cutvals, /**< values of variables in cut */
3784 SCIP_Real* varsolvals, /**< solution value of variables */
3785 SCIP_Real* weights, /**< weights to compute cmir cut */
3786 int* nprevrows, /**< number of previously generated rows */
3787 SCIP_ROW** prevrows, /**< previously generated rows */
3788 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
3789 unsigned int* ngen /**< number of generated cuts */
3790 )
3791{
3792 char name[SCIP_MAXSTRLEN];
3793 SCIP_Longint maxdnom;
3794 SCIP_Bool cutislocal;
3795 SCIP_Real maxscale;
3796 SCIP_Real cutrhs;
3797 SCIP_Real cutefficacy;
3798 SCIP_Bool success;
3799 SCIP_ROW** rows;
3800 SCIP_VAR** vars;
3801 SCIP* subscip;
3802 int nrows;
3803 int nvars;
3804 int k;
3805 int cutrank;
3806 int cutnnz;
3807
3808 assert( scip != NULL );
3809 assert( sepadata != NULL );
3810 assert( mipdata != NULL );
3811 assert( sol != NULL );
3812 assert( cutcoefs != NULL );
3813 assert( cutinds != NULL );
3814 assert( cutvals != NULL );
3815 assert( varsolvals != NULL );
3816 assert( weights != NULL );
3817 assert( nprevrows != NULL );
3818 assert( prevrows != NULL );
3819 assert( cutoff != NULL );
3820 assert( ngen != NULL );
3821
3822 *cutoff = FALSE;
3823 subscip = mipdata->subscip;
3824 assert( subscip != NULL );
3825
3826 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
3827 assert( nrows > 0 );
3828 assert( (int) mipdata->nrows == nrows );
3829
3830 /* @todo more advanced settings - compare sepa_gomory.c */
3831 maxdnom = (SCIP_Longint) sepadata->cutcoefbnd + 1;
3832 maxscale = 10000.0;
3833
3834 /* get variable data */
3835 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3836
3837 /* generate weights */
3838 for (k = 0; k < nrows; ++k)
3839 {
3840 SCIP_Real val;
3841
3842 weights[k] = 0;
3843 if ( mipdata->ylhs[k] != NULL )
3844 {
3845 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3846
3847 val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[k]);
3848 assert( ! SCIPisFeasNegative(subscip, val) );
3849
3850 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3851 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3852
3853 if ( SCIPisFeasPositive(subscip, val) )
3854 weights[k] = -val;
3855 }
3856
3857 if ( mipdata->yrhs[k] != NULL )
3858 {
3859 assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3860
3861 val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[k]);
3862 assert( ! SCIPisFeasNegative(subscip, val) );
3863
3864 assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3865 val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3866
3867 /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
3868 if ( SCIPisFeasGT(scip, val, ABS(weights[k])) )
3869 weights[k] = val;
3870 }
3871 }
3872
3873 /* create a strong CG cut out of the weighted LP rows using the B^-1 row as weights */
3874 cutefficacy = -1.0;
3875 cutrhs = -1.0;
3876 SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, weights, NULL, -1, FALSE,
3877 sepadata->allowlocal, 1, (int) MAXAGGRLEN(nvars), &success) );
3878
3879 if ( ! success )
3880 return SCIP_OKAY;
3881
3882 SCIP_CALL( SCIPcalcStrongCG(scip, NULL, POSTPROCESS, BOUNDSWITCH, VARTYPEUSEVBDS, sepadata->allowlocal, MINFRAC, MAXFRAC,
3883 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
3884
3885 assert( sepadata->allowlocal || !cutislocal );
3886 SCIPdebugMsg(scip, "Strong-CG: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success,
3887 SCIPisEfficacious(scip, cutefficacy) ? " " : " not ", cutefficacy, cutrhs);
3888
3889 /* If successful, convert dense cut into sparse row, and add the row as a cut only if the cut if violated - if it is
3890 * not violated we might store non-local cuts in the pool. */
3891 if ( success && (SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) )
3892 {
3893 SCIP_ROW* cut;
3894
3895 /* create the cut */
3896 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
3897 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
3898
3899 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
3900
3901 for (k = 0; k < cutnnz; ++k)
3902 {
3903 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutcoefs[k]) );
3904 }
3905
3906 assert( success );
3907
3908 /* set cut rank */
3909 SCIProwChgRank(cut, cutrank);
3910
3911#ifdef SCIP_DEBUG
3912 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3913#else
3914 if ( sepadata->output )
3915 {
3916 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3917 }
3918#endif
3919
3920 /* try to scale the cut to integral values */
3921 SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
3922 maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
3923
3924 /* if the cut could be made integral */
3925 if ( success )
3926 {
3927 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
3928
3929 /* add cut to pool */
3930 if ( ! cutislocal )
3931 {
3932 assert( SCIPisEfficacious(scip, cutefficacy) || sepadata->usecutpool );
3933 SCIP_CALL( SCIPaddPoolCut(scip, cut) );
3934 }
3935
3936 if ( ! SCIPisCutEfficacious(scip, NULL, cut) )
3937 {
3938 SCIPdebugMsg(scip, " -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
3939 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3940 SCIPgetCutEfficacy(scip, NULL, cut));
3941
3942 /* release the row */
3943 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3944 }
3945 else
3946 {
3947 /* check whether cut has been found before - may happend due to projection */
3948 for (k = 0; k < *nprevrows; ++k)
3949 {
3950 SCIP_Real parval;
3951
3952 assert( prevrows[k] != NULL );
3953 parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
3954 /* exit if row is parallel to existing cut and rhs is not better */
3955 if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
3956 break;
3957 }
3958
3959 /* if cut is new */
3960 if ( k >= *nprevrows )
3961 {
3962 prevrows[*nprevrows] = cut;
3963 ++(*nprevrows);
3964
3965 SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n",
3966 name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3967 SCIPgetCutEfficacy(scip, NULL, cut), SCIProwGetRank(cut),
3968 SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
3969 SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
3970#ifdef SCIP_OUTPUT
3971 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3972#else
3973 if ( sepadata->output )
3974 {
3975 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3976 }
3977#endif
3978 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
3979 ++(*ngen);
3980 }
3981 else
3982 {
3983 SCIPdebugMsg(scip, "Cut already exists.\n");
3984 /* release the row */
3985 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3986 }
3987 }
3988 }
3989 else
3990 {
3991 SCIPdebugMsg(scip, " -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n",
3992 name, cutefficacy, cutrhs);
3993
3994 /* release the row */
3995 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3996 }
3997 }
3998
3999 return SCIP_OKAY;
4000}
4001
4002
4003/** Create CG-cuts from solutions of sub-MIP */
4004static
4005SCIP_RETCODE createCGCuts(
4006 SCIP* scip, /**< SCIP data structure */
4007 SCIP_SEPA* sepa, /**< separator */
4008 SCIP_SEPADATA* sepadata, /**< separator data */
4009 CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
4010 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
4011 unsigned int* ngen /**< number of generated cuts */
4012 )
4013{
4014 SCIP_BOUNDTYPE* boundtypesfortrans;
4015 SCIP_STAGE stage;
4016 SCIP_AGGRROW* aggrrow = NULL;
4017 SCIP_Real* varsolvals;
4018 SCIP_Real* weights;
4019 int* cutinds;
4020 SCIP_Real* cutvals;
4021 SCIP_Real* cutcoefs;
4022 SCIP_ROW** prevrows;
4023 SCIP_SOL** sols;
4024 SCIP_VAR** vars;
4025 SCIP* subscip;
4026 int* boundsfortrans;
4027 int nprevrows;
4028 int ntotalrows;
4029 int nsols;
4030 int nvars;
4031 int k;
4032 int s;
4033
4034 assert( scip != NULL );
4035 assert( sepadata != NULL );
4036 assert( mipdata != NULL );
4037 assert( cutoff != NULL );
4038 assert( ngen != NULL );
4039
4040 subscip = mipdata->subscip;
4041 assert( subscip != NULL );
4042
4043 *cutoff = FALSE;
4044 *ngen = 0;
4045
4046 /* check if solving was successful and get solutions */
4047 stage = SCIPgetStage(subscip);
4048 if ( stage == SCIP_STAGE_SOLVING || stage == SCIP_STAGE_SOLVED )
4049 nsols = SCIPgetNSols(subscip);
4050 else
4051 nsols = 0;
4052
4053 /* only if solutions have been found */
4054 if ( nsols == 0 )
4055 return SCIP_OKAY;
4056
4057 SCIPdebugMsg(scip, "Generating CG-cuts from %d sols (cmir: %u, strong-cg: %u) ...\n", nsols, sepadata->usecmir, sepadata->usestrongcg);
4058
4059 sols = SCIPgetSols(subscip);
4060
4061 /* get variable data */
4062 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
4063
4064 /* allocate temporary memory */
4065 assert(mipdata->ntotalrows <= INT_MAX);
4066 ntotalrows = (int)mipdata->ntotalrows;
4067 assert( ntotalrows >= SCIPgetNLPRows(scip) && ntotalrows <= SCIPgetNLPRows(scip) + 1 );
4068 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
4069 SCIP_CALL( SCIPallocBufferArray(scip, &varsolvals, nvars) );
4070 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) );
4071 SCIP_CALL( SCIPallocBufferArray(scip, &cutvals, nvars) );
4072 SCIP_CALL( SCIPallocBufferArray(scip, &weights, ntotalrows) );
4073 SCIP_CALL( SCIPallocBufferArray(scip, &prevrows, 2 * nsols) );
4074
4075 if ( sepadata->usecmir || sepadata->usestrongcg )
4076 {
4077 SCIP_CALL( SCIPaggrRowCreate(scip, &aggrrow) );
4078 }
4079
4080 /* prepare arrays for bound information, if requested */
4081 if ( sepadata->usecmir && sepadata->cmirownbounds )
4082 {
4083 SCIP_CALL( SCIPallocBufferArray(scip, &boundsfortrans, nvars) );
4084 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypesfortrans, nvars) );
4085 }
4086 else
4087 {
4088 boundsfortrans = NULL;
4089 boundtypesfortrans = NULL;
4090 }
4091
4092 /* get solution values */
4093 for (k = 0; k < nvars; ++k)
4094 {
4095 if ( SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_COLUMN )
4096 varsolvals[k] = SCIPvarGetLPSol(vars[k]);
4097 else
4098 varsolvals[k] = 0.0;
4099 }
4100
4101 /* loop through solutions found */
4102 nprevrows = 0;
4103 for (s = 0; s < nsols; ++s)
4104 {
4105 SCIP_SOL* sol;
4106 sol = sols[s];
4107
4108 /* generate cuts by the C-MIR and/or Strong-CG functions */
4109 if ( sepadata->usecmir )
4110 {
4111 SCIP_CALL( createCGCutCMIR(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights,
4112 boundsfortrans, boundtypesfortrans, &nprevrows, prevrows, cutoff, ngen) );
4113 }
4114
4115 if ( sepadata->usestrongcg )
4116 {
4117 SCIP_CALL( createCGCutStrongCG(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights,
4118 &nprevrows, prevrows, cutoff, ngen) );
4119 }
4120
4121 if ( ! sepadata->usecmir && ! sepadata->usestrongcg )
4122 {
4123 SCIP_CALL( createCGCutDirect(scip, sepa, sepadata, mipdata, sol, cutcoefs, cutinds, cutvals, varsolvals, weights,
4124 &nprevrows, prevrows, cutoff, ngen) );
4125
4126 assert(! sepadata->usecmir && ! sepadata->usestrongcg);
4127 }
4128 }
4129 assert( nprevrows <= 2 * nsols );
4130 assert( sepadata->usecmir || nprevrows <= nsols );
4131 assert( sepadata->usestrongcg || nprevrows <= nsols );
4132
4133 /* release rows */
4134 for (k = 0; k < nprevrows; ++k)
4135 {
4136 SCIP_CALL( SCIPreleaseRow(scip, &(prevrows[k])) );
4137 }
4138
4139 if ( sepadata->usecmir || sepadata->usestrongcg )
4140 SCIPaggrRowFree(scip, &aggrrow);
4141
4142 /* free temporary memory */
4143 SCIPfreeBufferArrayNull(scip, &boundsfortrans);
4144 SCIPfreeBufferArrayNull(scip, &boundtypesfortrans);
4145
4146 SCIPfreeBufferArray(scip, &prevrows);
4147 SCIPfreeBufferArray(scip, &weights);
4148 SCIPfreeBufferArray(scip, &cutvals);
4149 SCIPfreeBufferArray(scip, &cutinds);
4150 SCIPfreeBufferArray(scip, &varsolvals);
4151 SCIPfreeBufferArray(scip, &cutcoefs);
4152
4153 return SCIP_OKAY;
4154}
4155
4156
4157/** frees "subscip" data */
4158static
4159SCIP_RETCODE freeSubscip(
4160 SCIP* scip, /**< SCIP data structure */
4161 SCIP_SEPA* sepa, /**< separator data */
4162 CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
4163 )
4164{
4165 SCIP_SEPADATA* sepadata;
4166 unsigned int i, j;
4167 SCIP* subscip;
4168
4169 assert( scip != NULL );
4170 assert( sepa != NULL );
4171 assert( mipdata != NULL );
4172
4173 /* free separator data */
4174 sepadata = SCIPsepaGetData(sepa);
4175 assert( sepadata != NULL );
4176
4177 SCIPdebugMsg(scip, "Freeing subscip ...\n");
4178
4179 subscip = mipdata->subscip;
4180 assert( subscip != NULL );
4181
4182 for (j = 0; j < mipdata->ncols; ++j)
4183 {
4184 if ( mipdata->coltype[j] == colPresent )
4185 {
4186 assert( mipdata->alpha[j] != NULL );
4187 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->alpha[j])) );
4188 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->fracalpha[j])) );
4189 }
4190 }
4191 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->beta)) );
4192 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->fracbeta)) );
4193
4194 for (i = 0; i < mipdata->nrows; ++i)
4195 {
4196 if ( mipdata->ylhs[i] != NULL )
4197 {
4198 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->ylhs[i])) );
4199 }
4200 if ( mipdata->yrhs[i] != NULL )
4201 {
4202 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->yrhs[i])) );
4203 }
4204 }
4205
4206 if ( sepadata->useobjub || sepadata->useobjlb )
4207 {
4208 if ( mipdata->yrhs[mipdata->nrows] )
4209 {
4210 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->yrhs[mipdata->nrows])) );
4211 }
4212 if ( mipdata->ylhs[mipdata->nrows] )
4213 {
4214 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->ylhs[mipdata->nrows])) );
4215 }
4216 }
4217
4218 for (j = 0; j < mipdata->ncols; ++j)
4219 {
4220 if ( mipdata->z[j] != NULL )
4221 {
4222 SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->z[j])) );
4223 }
4224 }
4225
4226 SCIP_CALL( SCIPfree(&(mipdata->subscip)) );
4227
4228 SCIPfreeBlockMemoryArray(scip, &(mipdata->rhs), mipdata->ntotalrows);
4229 SCIPfreeBlockMemoryArray(scip, &(mipdata->lhs), mipdata->ntotalrows);
4230 SCIPfreeBlockMemoryArray(scip, &(mipdata->z), 2*mipdata->ncols); /*lint !e647*/
4231 SCIPfreeBlockMemoryArray(scip, &(mipdata->yrhs), mipdata->ntotalrows);
4232 SCIPfreeBlockMemoryArray(scip, &(mipdata->ylhs), mipdata->ntotalrows);
4233 SCIPfreeBlockMemoryArray(scip, &(mipdata->isshifted), mipdata->ncols);
4234 SCIPfreeBlockMemoryArray(scip, &(mipdata->iscomplemented), mipdata->ncols);
4235 SCIPfreeBlockMemoryArray(scip, &(mipdata->coltype), mipdata->ncols);
4236 SCIPfreeBlockMemoryArray(scip, &(mipdata->fracalpha), mipdata->ncols);
4237 SCIPfreeBlockMemoryArray(scip, &(mipdata->alpha), mipdata->ncols);
4238
4239 return SCIP_OKAY;
4240}
4241
4242
4243/*
4244 * Callback methods
4245 */
4246
4247
4248/** initialization method of separator (called after problem was transformed) */
4249static
4250SCIP_DECL_SEPAINIT(sepaInitCGMIP)
4251{
4252 SCIP_SEPADATA* sepadata;
4253
4254 sepadata = SCIPsepaGetData(sepa);
4255 assert(sepadata != NULL);
4256
4257 /* create and initialize random number generator */
4258 SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, DEFAULT_RANDSEED, TRUE) );
4259
4260 return SCIP_OKAY;
4261}
4262
4263/** deinitialization method of separator (called before transformed problem is freed) */
4264static
4265SCIP_DECL_SEPAEXIT(sepaExitCGMIP)
4266{ /*lint --e{715}*/
4267 SCIP_SEPADATA* sepadata;
4268
4269 sepadata = SCIPsepaGetData(sepa);
4270 assert(sepadata != NULL);
4271
4272 SCIPfreeRandom(scip, &sepadata->randnumgen);
4273
4274 return SCIP_OKAY;
4275}
4276
4277/** copy method for separator plugins (called when SCIP copies plugins) */
4278static
4279SCIP_DECL_SEPACOPY(sepaCopyCGMIP)
4280{ /*lint --e{715}*/
4281 assert( scip != NULL );
4282 assert( sepa != NULL );
4283 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
4284
4285 /* call inclusion method of constraint handler */
4286 SCIP_CALL( SCIPincludeSepaCGMIP(scip) );
4287
4288 return SCIP_OKAY;
4289}
4290
4291
4292/** destructor of separator to free user data (called when SCIP is exiting) */
4293static
4294SCIP_DECL_SEPAFREE(sepaFreeCGMIP)
4295{ /*lint --e{715}*/
4296 SCIP_SEPADATA* sepadata;
4297
4298 assert( scip != NULL );
4299 assert( sepa != NULL );
4300 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
4301
4302 /* free separator data */
4303 sepadata = SCIPsepaGetData(sepa);
4304 assert( sepadata != NULL );
4305
4306 SCIPfreeBlockMemory(scip, &sepadata);
4307
4308 SCIPsepaSetData(sepa, NULL);
4309
4310 return SCIP_OKAY;
4311}
4312
4313
4314/** LP solution separation method of separator */
4315static
4316SCIP_DECL_SEPAEXECLP(sepaExeclpCGMIP)
4317{ /*lint --e{715}*/
4318 SCIP_SEPADATA* sepadata;
4319 CGMIP_MIPDATA* mipdata;
4320
4321 int ncalls;
4322 int ncols;
4323 int nrows;
4324 unsigned int ngen = 0;
4325 SCIP_Bool success;
4326 SCIP_Bool cutoff = FALSE;
4327
4328 assert( scip != NULL );
4329 assert( sepa != NULL );
4330 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
4331 assert( result != NULL );
4332
4333 *result = SCIP_DIDNOTRUN;
4334
4335 sepadata = SCIPsepaGetData(sepa);
4336 assert(sepadata != NULL);
4337
4338 /* only call separator, if we are not close to terminating */
4339 if ( SCIPisStopped(scip) )
4340 return SCIP_OKAY;
4341
4342 /* only call separator up to a maximum depth */
4343 if ( sepadata->maxdepth >= 0 && depth > sepadata->maxdepth )
4344 return SCIP_OKAY;
4345
4346 /* only call separator a given number of times at each node */
4347 ncalls = SCIPsepaGetNCallsAtNode(sepa);
4348 if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
4349 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
4350 return SCIP_OKAY;
4351
4352 /* only call separator, if an optimal LP solution is at hand */
4353 if ( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
4354 return SCIP_OKAY;
4355
4356 /* skip separation if there are continuous variables, but only integers required */
4357 if ( SCIPgetNContVars(scip) > 0 && sepadata->onlyintvars )
4358 return SCIP_OKAY;
4359
4360 /* only call separator, if there are fractional variables */
4361 if ( SCIPgetNLPBranchCands(scip) == 0 )
4362 return SCIP_OKAY;
4363
4364 /* check for parameters */
4365 if ( ( sepadata->useobjub || sepadata->useobjlb ) && ( sepadata->usecmir || sepadata->usestrongcg ) )
4366 {
4367 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
4368 "WARNING - sepa_cgmip: Using objective function bounds and CMIR or Strong-CG functions is useless. Turning off usage of objective function bounds.\n");
4369 SCIP_CALL( SCIPsetBoolParam(scip, "separating/cgmip/useobjub", FALSE) );
4370 SCIP_CALL( SCIPsetBoolParam(scip, "separating/cgmip/useobjlb", FALSE) );
4371 }
4372 sepadata->allowlocal = allowlocal;
4373
4374 /* get LP data */
4375 ncols = SCIPgetNLPCols(scip);
4376 nrows = SCIPgetNLPRows(scip);
4377 if ( ncols <= NCOLSTOOSMALL || nrows <= NROWSTOOSMALL )
4378 return SCIP_OKAY;
4379
4380 /* determine whether we should run the separation based on a decision tree */
4381 if ( sepadata->decisiontree )
4382 {
4383 SCIP_Bool separate;
4384 SCIP_Real firstlptime;
4385
4386 separate = FALSE;
4387 firstlptime = SCIPgetFirstLPTime(scip);
4388
4389 if ( nrows <= 136 && firstlptime <= 0.05 && ncols <= 143 )
4390 separate = TRUE;
4391 else if ( nrows <= 136 && 0.05 < firstlptime && firstlptime <= 0.15 && ncols <= 143 )
4392 separate = TRUE;
4393 else if ( 136 < nrows && nrows <= 332 && ncols <= 143 )
4394 separate = TRUE;
4395 else if ( 136 < nrows && nrows <= 332 && 655 < ncols && ncols <= 1290 )
4396 separate = TRUE;
4397 else if ( 333 < nrows && nrows <= 874 && 0.15 < firstlptime && firstlptime <= 0.25 && 2614 < ncols && ncols <= 5141 )
4398 separate = TRUE;
4399 else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 143 < ncols && ncols <= 265 )
4400 separate = TRUE;
4401 else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 265 < ncols && ncols <= 654 )
4402 separate = TRUE;
4403 else if ( 875 < nrows && nrows <= 1676 && 0.05 < firstlptime && firstlptime <= 0.15 )
4404 separate = TRUE;
4405 else if ( 875 < nrows && nrows <= 1676 && 0.15 < firstlptime && firstlptime <= 0.25 && 1291 < ncols && ncols <= 2613 )
4406 separate = TRUE;
4407 else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 655 < ncols && ncols <= 1290 )
4408 separate = TRUE;
4409 else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 1291 < ncols && ncols <= 2613 )
4410 separate = TRUE;
4411 else if ( nrows > 8146 && firstlptime > 6.25 )
4412 separate = TRUE;
4413
4414 if ( ! separate )
4415 {
4416 return SCIP_OKAY;
4417 }
4418 }
4419
4420 /* preceed with separation */
4421 *result = SCIP_DIDNOTFIND;
4422
4423 SCIPdebugMsg(scip, "separating CG-cuts via sub-MIPs: %d cols, %d rows\n", ncols, nrows);
4424
4425 /* prepare data */
4426 SCIP_CALL( SCIPallocBlockMemory(scip, &mipdata) );
4427 mipdata->subscip = NULL;
4428 mipdata->alpha = NULL;
4429 mipdata->fracalpha = NULL;
4430 mipdata->beta = NULL;
4431 mipdata->fracbeta = NULL;
4432 mipdata->coltype = NULL;
4433 mipdata->iscomplemented = NULL;
4434 mipdata->isshifted = NULL;
4435 mipdata->ylhs = NULL;
4436 mipdata->yrhs = NULL;
4437 mipdata->z = NULL;
4438 mipdata->lhs = NULL;
4439 mipdata->rhs = NULL;
4440 mipdata->normtype = ' ';
4441
4442 mipdata->conshdlrfullnorm = CONSHDLRFULLNORM;
4443 mipdata->scip = scip;
4444 mipdata->sepa = sepa;
4445 mipdata->sepadata = sepadata;
4446
4447 /* get the type of norm to use for efficacy calculations */
4448 SCIP_CALL( SCIPgetCharParam(scip, "separating/efficacynorm", &mipdata->normtype) );
4449
4450 /* create subscip */
4451 SCIP_CALL( createSubscip(scip, sepa, sepadata, mipdata) );
4452
4453 /* set parameters */
4454 SCIP_CALL( subscipSetParams(sepadata, mipdata) );
4455
4456 if ( ! SCIPisStopped(scip) )
4457 {
4458 /* solve subscip */
4459 SCIP_CALL( solveSubscip(scip, sepadata, mipdata, &success) );
4460
4461 /* preceed if solution was successful */
4462 if ( success && ! SCIPisStopped(scip) )
4463 {
4464 SCIP_CALL( createCGCuts(scip, sepa, sepadata, mipdata, &cutoff, &ngen) );
4465 }
4466 }
4467
4468 SCIP_CALL( freeSubscip(scip, sepa, mipdata) );
4469 SCIPfreeBlockMemory(scip, &mipdata);
4470
4471 SCIPdebugMsg(scip, "Found %u CG-cuts.\n", ngen);
4472
4473 if ( cutoff )
4474 *result = SCIP_CUTOFF;
4475 else if ( ngen > 0 )
4476 *result = SCIP_SEPARATED;
4477
4478#ifdef SCIP_OUTPUT
4479 /* SCIP_CALL( SCIPwriteLP(scip, "cuts.lp") ); */
4480 /* SCIP_CALL( SCIPwriteMIP(scip, "cuts.lp", FALSE, TRUE) ); */
4481#endif
4482
4483 return SCIP_OKAY;
4484}
4485
4486/*
4487 * separator specific interface methods
4488 */
4489
4490/** creates the CGMIP MIR cut separator and includes it in SCIP */
4491SCIP_RETCODE SCIPincludeSepaCGMIP(
4492 SCIP* scip /**< SCIP data structure */
4493 )
4494{
4495 SCIP_SEPADATA* sepadata;
4496 SCIP_SEPA* sepa = NULL;
4497
4498 /* create separator data */
4499 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
4500
4501 /* include separator */
4502 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
4503 SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpCGMIP, NULL, sepadata) );
4504 assert(sepa != NULL);
4505
4506 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyCGMIP) );
4507 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeCGMIP) );
4508 SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitCGMIP) );
4509 SCIP_CALL( SCIPsetSepaExit(scip, sepa, sepaExitCGMIP) );
4510
4511 /* add separator parameters */
4512 SCIP_CALL( SCIPaddIntParam(scip,
4513 "separating/" SEPA_NAME "/maxrounds",
4514 "maximal number of cgmip separation rounds per node (-1: unlimited)",
4515 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
4516
4517 SCIP_CALL( SCIPaddIntParam(scip,
4518 "separating/" SEPA_NAME "/maxroundsroot",
4519 "maximal number of cgmip separation rounds in the root node (-1: unlimited)",
4520 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
4521
4522 SCIP_CALL( SCIPaddIntParam(scip,
4523 "separating/" SEPA_NAME "/maxdepth",
4524 "maximal depth at which the separator is applied (-1: unlimited)",
4525 &sepadata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
4526
4527 SCIP_CALL( SCIPaddBoolParam(scip,
4528 "separating/" SEPA_NAME "/decisiontree",
4529 "Use decision tree to turn separation on/off?",
4530 &sepadata->decisiontree, FALSE, DEFAULT_DECISIONTREE, NULL, NULL) );
4531
4532 SCIP_CALL( SCIPaddRealParam(scip,
4533 "separating/" SEPA_NAME "/timelimit",
4534 "time limit for sub-MIP",
4535 &sepadata->timelimit, TRUE, DEFAULT_TIMELIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4536
4537 SCIP_CALL( SCIPaddRealParam(scip,
4538 "separating/" SEPA_NAME "/memorylimit",
4539 "memory limit for sub-MIP",
4540 &sepadata->memorylimit, TRUE, DEFAULT_MEMORYLIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4541
4542 SCIP_CALL( SCIPaddLongintParam(scip,
4543 "separating/" SEPA_NAME "/minnodelimit",
4544 "minimum number of nodes considered for sub-MIP (-1: unlimited)",
4545 &sepadata->minnodelimit, FALSE, DEFAULT_MINNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
4546
4547 SCIP_CALL( SCIPaddLongintParam(scip,
4548 "separating/" SEPA_NAME "/maxnodelimit",
4549 "maximum number of nodes considered for sub-MIP (-1: unlimited)",
4550 &sepadata->maxnodelimit, FALSE, DEFAULT_MAXNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
4551
4552 SCIP_CALL( SCIPaddRealParam(scip,
4553 "separating/" SEPA_NAME "/cutcoefbnd",
4554 "bounds on the values of the coefficients in the CG-cut",
4555 &sepadata->cutcoefbnd, TRUE, DEFAULT_CUTCOEFBND, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4556
4557 SCIP_CALL( SCIPaddBoolParam(scip,
4558 "separating/" SEPA_NAME "/onlyactiverows",
4559 "Use only active rows to generate cuts?",
4560 &sepadata->onlyactiverows, FALSE, DEFAULT_ONLYACTIVEROWS, NULL, NULL) );
4561
4562 SCIP_CALL( SCIPaddIntParam(scip,
4563 "separating/" SEPA_NAME "/maxrowage",
4564 "maximal age of rows to consider if onlyactiverows is false",
4565 &sepadata->maxrowage, FALSE, DEFAULT_MAXROWAGE, -1, INT_MAX, NULL, NULL) );
4566
4567 SCIP_CALL( SCIPaddBoolParam(scip,
4568 "separating/" SEPA_NAME "/onlyrankone",
4569 "Separate only rank 1 inequalities w.r.t. CG-MIP separator?",
4570 &sepadata->onlyrankone, FALSE, DEFAULT_ONLYRANKONE, NULL, NULL) );
4571
4572 SCIP_CALL( SCIPaddBoolParam(scip,
4573 "separating/" SEPA_NAME "/onlyintvars",
4574 "Generate cuts for problems with only integer variables?",
4575 &sepadata->onlyintvars, FALSE, DEFAULT_ONLYINTVARS, NULL, NULL) );
4576
4577 SCIP_CALL( SCIPaddBoolParam(scip,
4578 "separating/" SEPA_NAME "/contconvert",
4579 "Convert some integral variables to be continuous to reduce the size of the sub-MIP?",
4580 &sepadata->contconvert, FALSE, DEFAULT_CONTCONVERT, NULL, NULL) );
4581
4582 SCIP_CALL( SCIPaddRealParam(scip,
4583 "separating/" SEPA_NAME "/contconvfrac",
4584 "fraction of integral variables converted to be continuous (if contconvert)",
4585 &sepadata->contconvfrac, FALSE, DEFAULT_CONTCONVFRAC, 0.0, 1.0, NULL, NULL) );
4586
4587 SCIP_CALL( SCIPaddIntParam(scip,
4588 "separating/" SEPA_NAME "/contconvmin",
4589 "minimum number of integral variables before some are converted to be continuous",
4590 &sepadata->contconvmin, FALSE, DEFAULT_CONTCONVMIN, -1, INT_MAX, NULL, NULL) );
4591
4592 SCIP_CALL( SCIPaddBoolParam(scip,
4593 "separating/" SEPA_NAME "/intconvert",
4594 "Convert some integral variables attaining fractional values to have integral value?",
4595 &sepadata->intconvert, FALSE, DEFAULT_INTCONVERT, NULL, NULL) );
4596
4597 SCIP_CALL( SCIPaddRealParam(scip,
4598 "separating/" SEPA_NAME "/intconvfrac",
4599 "fraction of frac. integral variables converted to have integral value (if intconvert)",
4600 &sepadata->intconvfrac, FALSE, DEFAULT_INTCONVFRAC, 0.0, 1.0, NULL, NULL) );
4601
4602 SCIP_CALL( SCIPaddIntParam(scip,
4603 "separating/" SEPA_NAME "/intconvmin",
4604 "minimum number of integral variables before some are converted to have integral value",
4605 &sepadata->intconvmin, FALSE, DEFAULT_INTCONVMIN, -1, INT_MAX, NULL, NULL) );
4606
4607 SCIP_CALL( SCIPaddBoolParam(scip,
4608 "separating/" SEPA_NAME "/skipmultbounds",
4609 "Skip the upper bounds on the multipliers in the sub-MIP?",
4610 &sepadata->skipmultbounds, FALSE, DEFAULT_SKIPMULTBOUNDS, NULL, NULL) );
4611
4612 SCIP_CALL( SCIPaddBoolParam(scip,
4613 "separating/" SEPA_NAME "/objlone",
4614 "Should the objective of the sub-MIP minimize the l1-norm of the multipliers?",
4615 &sepadata->objlone, FALSE, DEFAULT_OBJLONE, NULL, NULL) );
4616
4617 SCIP_CALL( SCIPaddRealParam(scip,
4618 "separating/" SEPA_NAME "/objweight",
4619 "weight used for the row combination coefficient in the sub-MIP objective",
4620 &sepadata->objweight, TRUE, DEFAULT_OBJWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4621
4622 SCIP_CALL( SCIPaddBoolParam(scip,
4623 "separating/" SEPA_NAME "/objweightsize",
4624 "Weight each row by its size?",
4625 &sepadata->objweightsize, FALSE, DEFAULT_OBJWEIGHTSIZE, NULL, NULL) );
4626
4627 SCIP_CALL( SCIPaddBoolParam(scip,
4628 "separating/" SEPA_NAME "/dynamiccuts",
4629 "should generated cuts be removed from the LP if they are no longer tight?",
4630 &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
4631
4632 SCIP_CALL( SCIPaddBoolParam(scip,
4633 "separating/" SEPA_NAME "/usecmir",
4634 "use CMIR-generator (otherwise add cut directly)?",
4635 &sepadata->usecmir, FALSE, DEFAULT_USECMIR, NULL, NULL) );
4636
4637 SCIP_CALL( SCIPaddBoolParam(scip,
4638 "separating/" SEPA_NAME "/usestrongcg",
4639 "use strong CG-function to strengthen cut?",
4640 &sepadata->usestrongcg, FALSE, DEFAULT_USESTRONGCG, NULL, NULL) );
4641
4642 SCIP_CALL( SCIPaddBoolParam(scip,
4643 "separating/" SEPA_NAME "/cmirownbounds",
4644 "tell CMIR-generator which bounds to used in rounding?",
4645 &sepadata->cmirownbounds, FALSE, DEFAULT_CMIROWNBOUNDS, NULL, NULL) );
4646
4647 SCIP_CALL( SCIPaddBoolParam(scip,
4648 "separating/" SEPA_NAME "/usecutpool",
4649 "use cutpool to store CG-cuts even if the are not efficient?",
4650 &sepadata->usecutpool, FALSE, DEFAULT_USECUTPOOL, NULL, NULL) );
4651
4652 SCIP_CALL( SCIPaddBoolParam(scip,
4653 "separating/" SEPA_NAME "/primalseparation",
4654 "only separate cuts that are tight for the best feasible solution?",
4655 &sepadata->primalseparation, FALSE, DEFAULT_PRIMALSEPARATION, NULL, NULL) );
4656
4657 SCIP_CALL( SCIPaddBoolParam(scip,
4658 "separating/" SEPA_NAME "/earlyterm",
4659 "terminate separation if a violated (but possibly sub-optimal) cut has been found?",
4660 &sepadata->earlyterm, FALSE, DEFAULT_EARLYTERM, NULL, NULL) );
4661
4662 SCIP_CALL( SCIPaddBoolParam(scip,
4663 "separating/" SEPA_NAME "/addviolationcons",
4664 "add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?",
4665 &sepadata->addviolationcons, FALSE, DEFAULT_ADDVIOLATIONCONS, NULL, NULL) );
4666
4667 SCIP_CALL( SCIPaddBoolParam(scip,
4668 "separating/" SEPA_NAME "/addviolconshdlr",
4669 "add constraint handler to filter out violated cuts?",
4670 &sepadata->addviolconshdlr, FALSE, DEFAULT_ADDVIOLCONSHDLR, NULL, NULL) );
4671
4672 SCIP_CALL( SCIPaddBoolParam(scip,
4673 "separating/" SEPA_NAME "/conshdlrusenorm",
4674 "should the violation constraint handler use the norm of a cut to check for feasibility?",
4675 &sepadata->conshdlrusenorm, FALSE, DEFAULT_CONSHDLRUSENORM, NULL, NULL) );
4676
4677 SCIP_CALL( SCIPaddBoolParam(scip,
4678 "separating/" SEPA_NAME "/useobjub",
4679 "Use upper bound on objective function (via primal solution)?",
4680 &sepadata->useobjub, FALSE, DEFAULT_USEOBJUB, NULL, NULL) );
4681
4682 SCIP_CALL( SCIPaddBoolParam(scip,
4683 "separating/" SEPA_NAME "/useobjlb",
4684 "Use lower bound on objective function (via primal solution)?",
4685 &sepadata->useobjlb, FALSE, DEFAULT_USEOBJLB, NULL, NULL) );
4686
4687 SCIP_CALL( SCIPaddBoolParam(scip,
4688 "separating/" SEPA_NAME "/subscipfast",
4689 "Should the settings for the sub-MIP be optimized for speed?",
4690 &sepadata->subscipfast, FALSE, DEFAULT_SUBSCIPFAST, NULL, NULL) );
4691
4692 SCIP_CALL( SCIPaddBoolParam(scip,
4693 "separating/" SEPA_NAME "/output",
4694 "Should information about the sub-MIP and cuts be displayed?",
4695 &sepadata->output, FALSE, DEFAULT_OUTPUT, NULL, NULL) );
4696
4697 SCIP_CALL( SCIPaddBoolParam(scip,
4698 "separating/" SEPA_NAME "/genprimalsols",
4699 "Try to generate primal solutions from Gomory cuts?",
4700 &sepadata->genprimalsols, FALSE, DEFAULT_GENPRIMALSOLS, NULL, NULL) );
4701
4702 return SCIP_OKAY;
4703}
a
SCIP_VAR * a
Definition: circlepacking.c:66
r
SCIP_Real * r
Definition: circlepacking.c:59
cons_linear.h
Constraint handler for linear constraints in their most general form, .
cuts.h
methods for the aggregation rows
NULL
#define NULL
Definition: def.h:248
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:269
SCIP_Longint
#define SCIP_Longint
Definition: def.h:141
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:158
SCIP_INVALID
#define SCIP_INVALID
Definition: def.h:178
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
MIN
#define MIN(x, y)
Definition: def.h:224
SCIP_Real
#define SCIP_Real
Definition: def.h:156
ABS
#define ABS(x)
Definition: def.h:216
SQR
#define SQR(x)
Definition: def.h:199
TRUE
#define TRUE
Definition: def.h:93
FALSE
#define FALSE
Definition: def.h:94
MAX
#define MAX(x, y)
Definition: def.h:220
SCIP_LONGINT_FORMAT
#define SCIP_LONGINT_FORMAT
Definition: def.h:148
REALABS
#define REALABS(x)
Definition: def.h:182
SCIP_LONGINT_MAX
#define SCIP_LONGINT_MAX
Definition: def.h:142
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:355
SCIPcreateConsLinear
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_linear.c:17755
SCIPsetSubscipDepth
void SCIPsetSubscipDepth(SCIP *scip, int newdepth)
Definition: scip_copy.c:2609
SCIPcheckCopyLimits
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3249
SCIPgetSubscipDepth
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2588
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:759
SCIPfree
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:402
SCIPcreate
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:370
SCIPgetStatus
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:562
SCIPgetStage
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:444
SCIPgetNObjVars
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2616
SCIPaddVar
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1907
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2340
SCIPgetNImplVars
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2387
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1242
SCIPgetNContVars
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2569
SCIPwriteOrigProblem
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:742
SCIPsetObjlimit
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1661
SCIPgetVarsData
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:2115
SCIPaddCons
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3274
SCIPsetObjsense
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1417
SCIPcreateProb
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:119
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2293
SCIPisObjIntegral
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip_prob.c:1801
SCIPinfoMessage
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIPverbMessage
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIPwarningMessage
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIPaddLongintParam
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
SCIPisParamFixed
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
SCIPaddIntParam
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIPsetLongintParam
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIPaddRealParam
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIPsetIntParam
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIPsetSubscipsOff
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:904
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIPwriteParams
SCIP_RETCODE SCIPwriteParams(SCIP *scip, const char *filename, SCIP_Bool comments, SCIP_Bool onlychanged)
Definition: scip_param.c:813
SCIPsetPresolving
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:956
SCIPsetEmphasis
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip_param.c:882
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIPsetBoolParam
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIPsetRealParam
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIPsetSeparating
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:985
SCIPgetCharParam
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:326
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:436
SCIPcolGetLPPos
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:17487
SCIPcolGetVar
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17425
SCIPcolIsIntegral
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:17455
SCIPcolGetObj
SCIP_Real SCIPcolGetObj(SCIP_COL *col)
Definition: lp.c:17336
SCIPcolGetVals
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17555
SCIPcolGetRows
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17545
SCIPcolGetLb
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:17346
SCIPcolGetPrimsol
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:17379
SCIPcolGetUb
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:17356
SCIPcolGetNLPNonz
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:17534
SCIPincludeConshdlrBasic
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:181
SCIPsetConshdlrFree
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIPconshdlrGetData
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4336
SCIPreleaseCons
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1173
SCIPaddPoolCut
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:336
SCIPgetCutEfficacy
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:94
SCIPcalcMIR
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, int vartypeusevbds, 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:7923
SCIPaggrRowCreate
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:2668
SCIPisCutEfficacious
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:117
SCIPisEfficacious
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIPcalcStrongCG
SCIP_RETCODE SCIPcalcStrongCG(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, int vartypeusevbds, SCIP_Bool allowlocal, 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:13281
SCIPaggrRowFree
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:2700
SCIPaddRow
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:225
SCIPaggrRowSumRows
SCIP_RETCODE SCIPaggrRowSumRows(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid)
Definition: cuts.c:3523
SCIPgetLPBasisInd
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip_lp.c:692
SCIPgetLPColsData
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:477
SCIPgetLPRowsData
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:576
SCIPgetNLPRows
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:632
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:174
SCIPgetNLPCols
int SCIPgetNLPCols(SCIP *scip)
Definition: scip_lp.c:533
SCIPgetLPBInvRow
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:720
SCIPgetMemExternEstim
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:126
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
SCIPgetMemUsed
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:100
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIPallocBlockMemoryArray
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIPfreeBufferArrayNull
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIProwIsIntegral
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:17785
SCIPgetRowMaxCoef
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1886
SCIProwGetLhs
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17686
SCIPgetRowMinCoef
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1868
SCIProwIsModifiable
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17805
SCIPcacheRowExtensions
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1581
SCIProwGetParallelism
SCIP_Real SCIProwGetParallelism(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
Definition: lp.c:7970
SCIProwGetCols
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17632
SCIPgetRowLPActivity
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1957
SCIProwGetRhs
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17696
SCIProwGetAge
int SCIProwGetAge(SCIP_ROW *row)
Definition: lp.c:17765
SCIProwGetNLPNonz
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:17621
SCIProwGetNorm
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:17662
SCIProwGetLPPos
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17895
SCIPflushRowExtensions
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1604
SCIProwIsLocal
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17795
SCIPmakeRowIntegral
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
Definition: scip_lp.c:1790
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1646
SCIPprintRow
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2176
SCIProwGetName
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17745
SCIProwGetOriginSepa
SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
Definition: lp.c:17870
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1508
SCIPcreateEmptyRowSepa
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1429
SCIProwGetRank
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:17775
SCIProwChgRank
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17928
SCIProwGetConstant
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17652
SCIProwGetVals
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17642
SCIProwGetBasisStatus
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:17734
SCIPsetSepaExit
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
Definition: scip_sepa.c:205
SCIPincludeSepaBasic
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:115
SCIPsepaGetName
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:746
SCIPsepaGetNCallsAtNode
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:893
SCIPsetSepaFree
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:173
SCIPsepaGetData
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:636
SCIPsepaSetData
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:646
SCIPsetSepaCopy
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:157
SCIPsetSepaInit
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: scip_sepa.c:189
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2981
SCIPcreateSol
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:516
SCIPprintSol
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:2349
SCIPgetNSols
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2882
SCIPgetSols
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2931
SCIPtrySolFree
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:4109
SCIPsetSolVal
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1571
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1765
SCIPtransformProb
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:232
SCIPsolve
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2635
SCIPgetUpperbound
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip_solvingstats.c:1734
SCIPgetNNodes
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip_solvingstats.c:214
SCIPgetDualbound
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip_solvingstats.c:1428
SCIPprintStatistics
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip_solvingstats.c:5927
SCIPgetLowerbound
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip_solvingstats.c:1491
SCIPgetNLPs
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip_solvingstats.c:457
SCIPgetNLPIterations
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:503
SCIPgetFirstLPTime
SCIP_Real SCIPgetFirstLPTime(SCIP *scip)
Definition: scip_timing.c:468
SCIPgetSolvingTime
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIPisSumPositive
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:747
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:501
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:488
SCIPisIntegral
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:585
SCIPfeasFrac
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:932
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:771
SCIPisPositive
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:561
SCIPfeasCeil
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:908
SCIPisFeasZero
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:836
SCIPfloor
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:622
SCIPfeasFloor
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:896
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:512
SCIPisFeasLT
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:784
SCIPisFeasNegative
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:860
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:797
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:872
SCIPfrac
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:658
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:475
SCIPisNegative
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:573
SCIPisFeasGT
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:810
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:436
SCIPisSumZero
SCIP_Bool SCIPisSumZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:735
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:549
SCIPepsilon
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip_numerics.c:140
SCIPsumepsilon
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip_numerics.c:154
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:449
SCIPisFeasPositive
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:848
SCIPvarGetCol
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:23683
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:23386
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:24268
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:23900
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:24142
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:23662
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1887
SCIPvarIsIntegral
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:23490
SCIPvarGetLPSol
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:24664
SCIPgetVarSol
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:3051
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:24234
SCIPcreateVar
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:120
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:24120
SCIPfreeRandom
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:79
SCIPrandomGetReal
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10245
SCIPcreateRandom
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:56
SCIPincludeSepaCGMIP
SCIP_RETCODE SCIPincludeSepaCGMIP(SCIP *scip)
Definition: sepa_cgmip.c:4491
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10827
memory.h
memory allocation routines
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
pub_cons.h
public methods for managing constraints
pub_lp.h
public methods for LP management
pub_message.h
public methods for message output
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:64
pub_misc.h
public data structures and miscellaneous methods
pub_sepa.h
public methods for separators
pub_var.h
public methods for problem variables
scip_branch.h
public methods for branching rule plugins and branching
scip_cons.h
public methods for constraint handler plugins and constraints
scip_copy.h
public methods for problem copies
scip_cut.h
public methods for cuts and aggregation rows
scip_general.h
general public methods
scip_lp.h
public methods for the LP relaxation, rows and columns
scip_mem.h
public methods for memory management
scip_message.h
public methods for message handling
scip_numerics.h
public methods for numerical tolerances
scip_param.h
public methods for SCIP parameter handling
scip_prob.h
public methods for global and local (sub)problems
scip_randnumgen.h
public methods for random numbers
scip_sepa.h
public methods for separator plugins
scip_sol.h
public methods for solutions
scip_solve.h
public solving methods
scip_solvingstats.h
public methods for querying solving statistics
scip_timing.h
public methods for timing
scip_tree.h
public methods for the branch-and-bound tree
scip_var.h
public methods for SCIP variables
SCIPincludeDefaultPlugins
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
Definition: scipdefplugins.c:37
scipdefplugins.h
default SCIP plugins
DEFAULT_CUTCOEFBND
#define DEFAULT_CUTCOEFBND
Definition: sepa_cgmip.c:120
EPSILONVALUE
#define EPSILONVALUE
Definition: sepa_cgmip.c:158
SEPA_PRIORITY
#define SEPA_PRIORITY
Definition: sepa_cgmip.c:108
DEFAULT_USECUTPOOL
#define DEFAULT_USECUTPOOL
Definition: sepa_cgmip.c:141
DEFAULT_CONSHDLRUSENORM
#define DEFAULT_CONSHDLRUSENORM
Definition: sepa_cgmip.c:146
DEFAULT_ADDVIOLCONSHDLR
#define DEFAULT_ADDVIOLCONSHDLR
Definition: sepa_cgmip.c:145
createSubscip
static SCIP_RETCODE createSubscip(SCIP *origscip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:1047
DEFAULT_INTCONVMIN
#define DEFAULT_INTCONVMIN
Definition: sepa_cgmip.c:132
BOUNDSWITCH
#define BOUNDSWITCH
Definition: sepa_cgmip.c:167
SEPA_DELAY
#define SEPA_DELAY
Definition: sepa_cgmip.c:112
DEFAULT_ADDVIOLATIONCONS
#define DEFAULT_ADDVIOLATIONCONS
Definition: sepa_cgmip.c:144
createCGCutCMIR
static SCIP_RETCODE createCGCutCMIR(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
Definition: sepa_cgmip.c:3484
CONSHDLR_DESC
#define CONSHDLR_DESC
Definition: sepa_cgmip.c:283
solveSubscip
static SCIP_RETCODE solveSubscip(SCIP *origscip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *success)
Definition: sepa_cgmip.c:2444
DEFAULT_OBJWEIGHT
#define DEFAULT_OBJWEIGHT
Definition: sepa_cgmip.c:135
DEFAULT_SKIPMULTBOUNDS
#define DEFAULT_SKIPMULTBOUNDS
Definition: sepa_cgmip.c:133
MAXFRAC
#define MAXFRAC
Definition: sepa_cgmip.c:172
NROWSTOOSMALL
#define NROWSTOOSMALL
Definition: sepa_cgmip.c:155
DEFAULT_DYNAMICCUTS
#define DEFAULT_DYNAMICCUTS
Definition: sepa_cgmip.c:137
DEFAULT_MINNODELIMIT
#define DEFAULT_MINNODELIMIT
Definition: sepa_cgmip.c:121
DEFAULT_CONTCONVERT
#define DEFAULT_CONTCONVERT
Definition: sepa_cgmip.c:127
computeCut
static SCIP_RETCODE computeCut(SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Bool usefrac, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, SCIP_Bool *localrowsused, SCIP_Bool *localboundsused, int *cutrank, SCIP_Bool *success)
Definition: sepa_cgmip.c:2744
DEFAULT_USEOBJLB
#define DEFAULT_USEOBJLB
Definition: sepa_cgmip.c:148
POSTPROCESS
#define POSTPROCESS
Definition: sepa_cgmip.c:170
SEPA_DESC
#define SEPA_DESC
Definition: sepa_cgmip.c:107
createCGCutDirect
static SCIP_RETCODE createCGCutDirect(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
Definition: sepa_cgmip.c:3261
SCIP_DECL_SEPACOPY
static SCIP_DECL_SEPACOPY(sepaCopyCGMIP)
Definition: sepa_cgmip.c:4279
SCIP_DECL_CONSENFOLP
static SCIP_DECL_CONSENFOLP(consEnfolpViolatedCuts)
Definition: sepa_cgmip.c:526
CGMIP_ColType
CGMIP_ColType
Definition: sepa_cgmip.c:229
colConverted
@ colConverted
Definition: sepa_cgmip.c:232
colContinuous
@ colContinuous
Definition: sepa_cgmip.c:231
colPresent
@ colPresent
Definition: sepa_cgmip.c:230
colAtUb
@ colAtUb
Definition: sepa_cgmip.c:233
colAtLb
@ colAtLb
Definition: sepa_cgmip.c:234
MAKECONTINTEGRAL
#define MAKECONTINTEGRAL
Definition: sepa_cgmip.c:174
NCOLSTOOSMALL
#define NCOLSTOOSMALL
Definition: sepa_cgmip.c:156
DEFAULT_ONLYINTVARS
#define DEFAULT_ONLYINTVARS
Definition: sepa_cgmip.c:126
DEFAULT_DECISIONTREE
#define DEFAULT_DECISIONTREE
Definition: sepa_cgmip.c:117
DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_cgmip.c:115
SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP
Definition: sepa_cgmip.c:111
DEFAULT_GENPRIMALSOLS
#define DEFAULT_GENPRIMALSOLS
Definition: sepa_cgmip.c:152
DEFAULT_MAXDEPTH
#define DEFAULT_MAXDEPTH
Definition: sepa_cgmip.c:116
SCIP_DECL_SEPAINIT
static SCIP_DECL_SEPAINIT(sepaInitCGMIP)
Definition: sepa_cgmip.c:4250
computeObjWeightSize
static SCIP_Real computeObjWeightSize(int rowsize, int minrowsize, int maxrowsize)
Definition: sepa_cgmip.c:889
createCGCutStrongCG
static SCIP_RETCODE createCGCutStrongCG(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
Definition: sepa_cgmip.c:3774
DEFAULT_ONLYRANKONE
#define DEFAULT_ONLYRANKONE
Definition: sepa_cgmip.c:125
VARTYPEUSEVBDS
#define VARTYPEUSEVBDS
Definition: sepa_cgmip.c:168
DEFAULT_INTCONVERT
#define DEFAULT_INTCONVERT
Definition: sepa_cgmip.c:130
FIXINTEGRALRHS
#define FIXINTEGRALRHS
Definition: sepa_cgmip.c:173
DEFAULT_CMIROWNBOUNDS
#define DEFAULT_CMIROWNBOUNDS
Definition: sepa_cgmip.c:140
DEFAULT_OUTPUT
#define DEFAULT_OUTPUT
Definition: sepa_cgmip.c:150
DEFAULT_OBJLONE
#define DEFAULT_OBJLONE
Definition: sepa_cgmip.c:134
SCIP_DECL_CONSLOCK
static SCIP_DECL_CONSLOCK(consLockViolatedCuts)
Definition: sepa_cgmip.c:593
createCGMIPprimalsols
static SCIP_RETCODE createCGMIPprimalsols(SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:2195
DEFAULT_EARLYTERM
#define DEFAULT_EARLYTERM
Definition: sepa_cgmip.c:143
CONSHDLRFULLNORM
#define CONSHDLRFULLNORM
Definition: sepa_cgmip.c:161
CGMIP_MIPDATA
struct CGMIP_MIPData CGMIP_MIPDATA
Definition: sepa_cgmip.c:274
SCIPincludeConshdlrViolatedCut
static SCIP_RETCODE SCIPincludeConshdlrViolatedCut(SCIP *scip, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:602
DEFAULT_PRIMALSEPARATION
#define DEFAULT_PRIMALSEPARATION
Definition: sepa_cgmip.c:142
freeSubscip
static SCIP_RETCODE freeSubscip(SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:4159
SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST
Definition: sepa_cgmip.c:110
DEFAULT_CONTCONVMIN
#define DEFAULT_CONTCONVMIN
Definition: sepa_cgmip.c:129
MAXNSOLS
#define MAXNSOLS
Definition: sepa_cgmip.c:163
BETAEPSILONVALUE
#define BETAEPSILONVALUE
Definition: sepa_cgmip.c:159
SCIP_DECL_CONSENFOPS
static SCIP_DECL_CONSENFOPS(consEnfopsViolatedCuts)
Definition: sepa_cgmip.c:553
SEPA_FREQ
#define SEPA_FREQ
Definition: sepa_cgmip.c:109
MAXWEIGHTRANGE
#define MAXWEIGHTRANGE
Definition: sepa_cgmip.c:175
SCIP_DECL_SEPAEXECLP
static SCIP_DECL_SEPAEXECLP(sepaExeclpCGMIP)
Definition: sepa_cgmip.c:4316
SCIP_DECL_SEPAEXIT
static SCIP_DECL_SEPAEXIT(sepaExitCGMIP)
Definition: sepa_cgmip.c:4265
MINFRAC
#define MINFRAC
Definition: sepa_cgmip.c:171
DEFAULT_USEOBJUB
#define DEFAULT_USEOBJUB
Definition: sepa_cgmip.c:147
DEFAULT_RANDSEED
#define DEFAULT_RANDSEED
Definition: sepa_cgmip.c:151
MAXAGGRLEN
#define MAXAGGRLEN(nvars)
Definition: sepa_cgmip.c:179
DEFAULT_OBJWEIGHTSIZE
#define DEFAULT_OBJWEIGHTSIZE
Definition: sepa_cgmip.c:136
SCIP_DECL_CONSCHECK
static SCIP_DECL_CONSCHECK(consCheckViolatedCuts)
Definition: sepa_cgmip.c:567
storeCutInArrays
static SCIP_RETCODE storeCutInArrays(SCIP *scip, int nvars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, int *cutinds, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
Definition: sepa_cgmip.c:638
SEPA_NAME
#define SEPA_NAME
Definition: sepa_cgmip.c:106
SCIP_DECL_CONSFREE
static SCIP_DECL_CONSFREE(consFreeViolatedCuts)
Definition: sepa_cgmip.c:509
transformColumn
static SCIP_RETCODE transformColumn(SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_COL *col, SCIP_Real offset, SCIP_Real sigma, SCIP_Real *lhs, SCIP_Real *rhs, SCIP_Real *lb, SCIP_Real *ub, SCIP_Real *primsol)
Definition: sepa_cgmip.c:778
DEFAULT_ONLYACTIVEROWS
#define DEFAULT_ONLYACTIVEROWS
Definition: sepa_cgmip.c:123
subscipSetParams
static SCIP_RETCODE subscipSetParams(SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:2051
AWAY
#define AWAY
Definition: sepa_cgmip.c:176
DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS
Definition: sepa_cgmip.c:114
DEFAULT_MEMORYLIMIT
#define DEFAULT_MEMORYLIMIT
Definition: sepa_cgmip.c:119
DEFAULT_MAXROWAGE
#define DEFAULT_MAXROWAGE
Definition: sepa_cgmip.c:124
DEFAULT_USECMIR
#define DEFAULT_USECMIR
Definition: sepa_cgmip.c:138
OBJWEIGHTRANGE
#define OBJWEIGHTRANGE
Definition: sepa_cgmip.c:164
CONSHDLR_NAME
#define CONSHDLR_NAME
Definition: sepa_cgmip.c:282
solCutIsViolated
static SCIP_RETCODE solCutIsViolated(SCIP *scip, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Bool *violated)
Definition: sepa_cgmip.c:310
DEFAULT_SUBSCIPFAST
#define DEFAULT_SUBSCIPFAST
Definition: sepa_cgmip.c:149
MINEFFICACY
#define MINEFFICACY
Definition: sepa_cgmip.c:162
STALLNODELIMIT
#define STALLNODELIMIT
Definition: sepa_cgmip.c:160
DEFAULT_MAXNODELIMIT
#define DEFAULT_MAXNODELIMIT
Definition: sepa_cgmip.c:122
DEFAULT_CONTCONVFRAC
#define DEFAULT_CONTCONVFRAC
Definition: sepa_cgmip.c:128
createCGCuts
static SCIP_RETCODE createCGCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *cutoff, unsigned int *ngen)
Definition: sepa_cgmip.c:4005
DEFAULT_INTCONVFRAC
#define DEFAULT_INTCONVFRAC
Definition: sepa_cgmip.c:131
CGMIP_COLTYPE
enum CGMIP_ColType CGMIP_COLTYPE
Definition: sepa_cgmip.c:236
SCIP_DECL_SEPAFREE
static SCIP_DECL_SEPAFREE(sepaFreeCGMIP)
Definition: sepa_cgmip.c:4294
DEFAULT_TIMELIMIT
#define DEFAULT_TIMELIMIT
Definition: sepa_cgmip.c:118
DEFAULT_USESTRONGCG
#define DEFAULT_USESTRONGCG
Definition: sepa_cgmip.c:139
sepa_cgmip.h
Chvatal-Gomory cuts computed via a sub-MIP.
separate
static SCIP_RETCODE separate(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
Main separation function.
Definition: sepa_flower.c:1221
SCIP_AggrRow
Definition: struct_cuts.h:41
SCIP_Col
Definition: struct_lp.h:138
SCIP_Cons
Definition: struct_cons.h:47
SCIP_Conshdlr
Definition: struct_cons.h:128
SCIP_RandNumGen
Definition: struct_misc.h:270
SCIP_Row
Definition: struct_lp.h:205
SCIP_Sepa
Definition: struct_sepa.h:47
SCIP_Sol
Definition: struct_sol.h:74
SCIP_Var
Definition: struct_var.h:262
SCIP_CONSHDLRDATA
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
SCIP_BOUNDTYPE_UPPER
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:58
SCIP_BOUNDTYPE_LOWER
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:57
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:60
SCIP_LPSOLSTAT_OPTIMAL
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:44
SCIP_BASESTAT_UPPER
@ SCIP_BASESTAT_UPPER
Definition: type_lpi.h:93
SCIP_BASESTAT_LOWER
@ SCIP_BASESTAT_LOWER
Definition: type_lpi.h:91
SCIP_BASESTAT
enum SCIP_BaseStat SCIP_BASESTAT
Definition: type_lpi.h:96
SCIP_VERBLEVEL_NORMAL
@ SCIP_VERBLEVEL_NORMAL
Definition: type_message.h:60
SCIP_PARAMSETTING_FAST
@ SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:62
SCIP_PARAMEMPHASIS_FEASIBILITY
@ SCIP_PARAMEMPHASIS_FEASIBILITY
Definition: type_paramset.h:74
SCIP_OBJSENSE_MAXIMIZE
@ SCIP_OBJSENSE_MAXIMIZE
Definition: type_prob.h:47
SCIP_DIDNOTRUN
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
SCIP_CUTOFF
@ SCIP_CUTOFF
Definition: type_result.h:48
SCIP_FEASIBLE
@ SCIP_FEASIBLE
Definition: type_result.h:45
SCIP_DIDNOTFIND
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
SCIP_SEPARATED
@ SCIP_SEPARATED
Definition: type_result.h:49
SCIP_INFEASIBLE
@ SCIP_INFEASIBLE
Definition: type_result.h:46
SCIP_INVALIDDATA
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
SCIP_OKAY
@ SCIP_OKAY
Definition: type_retcode.h:42
SCIP_ERROR
@ SCIP_ERROR
Definition: type_retcode.h:43
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_SEPADATA
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52
SCIP_STAGE_SOLVED
@ SCIP_STAGE_SOLVED
Definition: type_set.h:54
SCIP_STAGE_SOLVING
@ SCIP_STAGE_SOLVING
Definition: type_set.h:53
SCIP_STAGE
enum SCIP_Stage SCIP_STAGE
Definition: type_set.h:59
SCIP_STATUS_OPTIMAL
@ SCIP_STATUS_OPTIMAL
Definition: type_stat.h:43
SCIP_STATUS_BESTSOLLIMIT
@ SCIP_STATUS_BESTSOLLIMIT
Definition: type_stat.h:60
SCIP_STATUS_USERINTERRUPT
@ SCIP_STATUS_USERINTERRUPT
Definition: type_stat.h:47
SCIP_STATUS_INFORUNBD
@ SCIP_STATUS_INFORUNBD
Definition: type_stat.h:46
SCIP_STATUS_STALLNODELIMIT
@ SCIP_STATUS_STALLNODELIMIT
Definition: type_stat.h:52
SCIP_STATUS_TIMELIMIT
@ SCIP_STATUS_TIMELIMIT
Definition: type_stat.h:54
SCIP_STATUS_INFEASIBLE
@ SCIP_STATUS_INFEASIBLE
Definition: type_stat.h:44
SCIP_STATUS_NODELIMIT
@ SCIP_STATUS_NODELIMIT
Definition: type_stat.h:49
SCIP_STATUS_MEMLIMIT
@ SCIP_STATUS_MEMLIMIT
Definition: type_stat.h:55
SCIP_STATUS
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:64
SCIP_VARTYPE_INTEGER
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:65
SCIP_VARTYPE_CONTINUOUS
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
SCIP_VARSTATUS_COLUMN
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:53