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