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
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"
94#include "scip/scip_sepa.h"
95#include "scip/scip_sol.h"
96#include "scip/scip_solve.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 */
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) */
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
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
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
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 */
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
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
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
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
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;
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);
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
1659 }
1660 else
1661 {
1662 SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, -1.0,
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,
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,
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,
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,
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,
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),
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
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 {
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) */
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 */
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 */
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
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
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
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
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
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) );
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
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),
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
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
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 */
3690 maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
3691
3692 /* if the cut could be made integral */
3693 if ( success )
3694 {
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),
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),
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
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
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
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 */
3921 maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
3922
3923 /* if the cut could be made integral */
3924 if ( success )
3925 {
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),
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),
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
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
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
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
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
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 */
4286
4287 return SCIP_OKAY;
4288}
4289
4290
4291/** destructor of separator to free user data (called when SCIP is exiting) */
4292static
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 */
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 {
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 */
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 */
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 */
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
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
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
4527 "separating/" SEPA_NAME "/decisiontree",
4528 "Use decision tree to turn separation on/off?",
4529 &sepadata->decisiontree, FALSE, DEFAULT_DECISIONTREE, NULL, NULL) );
4530
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
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
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
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
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
4557 "separating/" SEPA_NAME "/onlyactiverows",
4558 "Use only active rows to generate cuts?",
4559 &sepadata->onlyactiverows, FALSE, DEFAULT_ONLYACTIVEROWS, NULL, NULL) );
4560
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
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
4572 "separating/" SEPA_NAME "/onlyintvars",
4573 "Generate cuts for problems with only integer variables?",
4574 &sepadata->onlyintvars, FALSE, DEFAULT_ONLYINTVARS, NULL, NULL) );
4575
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
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
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
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
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
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
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
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
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
4622 "separating/" SEPA_NAME "/objweightsize",
4623 "Weight each row by its size?",
4624 &sepadata->objweightsize, FALSE, DEFAULT_OBJWEIGHTSIZE, NULL, NULL) );
4625
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
4632 "separating/" SEPA_NAME "/usecmir",
4633 "use CMIR-generator (otherwise add cut directly)?",
4634 &sepadata->usecmir, FALSE, DEFAULT_USECMIR, NULL, NULL) );
4635
4637 "separating/" SEPA_NAME "/usestrongcg",
4638 "use strong CG-function to strengthen cut?",
4639 &sepadata->usestrongcg, FALSE, DEFAULT_USESTRONGCG, NULL, NULL) );
4640
4642 "separating/" SEPA_NAME "/cmirownbounds",
4643 "tell CMIR-generator which bounds to used in rounding?",
4644 &sepadata->cmirownbounds, FALSE, DEFAULT_CMIROWNBOUNDS, NULL, NULL) );
4645
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
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
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
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
4667 "separating/" SEPA_NAME "/addviolconshdlr",
4668 "add constraint handler to filter out violated cuts?",
4669 &sepadata->addviolconshdlr, FALSE, DEFAULT_ADDVIOLCONSHDLR, NULL, NULL) );
4670
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
4677 "separating/" SEPA_NAME "/useobjub",
4678 "Use upper bound on objective function (via primal solution)?",
4679 &sepadata->useobjub, FALSE, DEFAULT_USEOBJUB, NULL, NULL) );
4680
4682 "separating/" SEPA_NAME "/useobjlb",
4683 "Use lower bound on objective function (via primal solution)?",
4684 &sepadata->useobjlb, FALSE, DEFAULT_USEOBJLB, NULL, NULL) );
4685
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
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
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}
SCIP_VAR * a
Definition: circlepacking.c:66
SCIP_Real * r
Definition: circlepacking.c:59
Constraint handler for linear constraints in their most general form, .
methods for the aggregation rows
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define ABS(x)
Definition: def.h:235
#define SQR(x)
Definition: def.h:214
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define REALABS(x)
Definition: def.h:197
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:374
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)
void SCIPsetSubscipDepth(SCIP *scip, int newdepth)
Definition: scip_copy.c:2626
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3253
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2605
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:498
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2220
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:601
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1422
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1242
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
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip_prob.c:1562
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:904
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIP_RETCODE SCIPwriteParams(SCIP *scip, const char *filename, SCIP_Bool comments, SCIP_Bool onlychanged)
Definition: scip_param.c:813
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip_param.c:882
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
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:979
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:326
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:17093
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:17072
SCIP_Real SCIPcolGetObj(SCIP_COL *col)
Definition: lp.c:16953
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17161
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17151
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:16963
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16996
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:16973
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:17140
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
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:94
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1723
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
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:117
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1755
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_RETCODE SCIPaggrRowSumRows(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid)
Definition: cuts.c:2279
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
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip_lp.c:686
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:471
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:626
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
int SCIPgetNLPCols(SCIP *scip)
Definition: scip_lp.c:527
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:714
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:126
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:100
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:17391
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1922
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1904
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17411
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIP_Real SCIProwGetParallelism(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
Definition: lp.c:7724
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17238
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1993
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
int SCIProwGetAge(SCIP_ROW *row)
Definition: lp.c:17371
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:17227
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:17268
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17501
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
Definition: scip_lp.c:1844
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
Definition: lp.c:17476
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1453
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:17381
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17534
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17258
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17248
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:17340
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
Definition: scip_sepa.c:199
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
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:880
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:633
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:643
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: scip_sepa.c:183
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1631
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2119
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:3050
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:222
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPgetFirstLPTime(SCIP *scip)
Definition: scip_timing.c:468
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisSumZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17789
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18452
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:2307
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
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
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
SCIP_RETCODE SCIPincludeSepaCGMIP(SCIP *scip)
Definition: sepa_cgmip.c:4490
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
public methods for managing constraints
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public data structures and miscellaneous methods
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for separator plugins
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
default SCIP plugins
#define DEFAULT_CUTCOEFBND
Definition: sepa_cgmip.c:120
#define EPSILONVALUE
Definition: sepa_cgmip.c:158
#define SEPA_PRIORITY
Definition: sepa_cgmip.c:108
#define DEFAULT_USECUTPOOL
Definition: sepa_cgmip.c:141
#define DEFAULT_CONSHDLRUSENORM
Definition: sepa_cgmip.c:146
#define DEFAULT_ADDVIOLCONSHDLR
Definition: sepa_cgmip.c:145
static SCIP_RETCODE createSubscip(SCIP *origscip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:1046
#define DEFAULT_INTCONVMIN
Definition: sepa_cgmip.c:132
#define BOUNDSWITCH
Definition: sepa_cgmip.c:167
#define SEPA_DELAY
Definition: sepa_cgmip.c:112
#define DEFAULT_ADDVIOLATIONCONS
Definition: sepa_cgmip.c:144
static SCIP_RETCODE createCGCutCMIR(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
Definition: sepa_cgmip.c:3483
#define CONSHDLR_DESC
Definition: sepa_cgmip.c:282
static SCIP_RETCODE solveSubscip(SCIP *origscip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *success)
Definition: sepa_cgmip.c:2443
#define DEFAULT_OBJWEIGHT
Definition: sepa_cgmip.c:135
#define DEFAULT_SKIPMULTBOUNDS
Definition: sepa_cgmip.c:133
#define MAXFRAC
Definition: sepa_cgmip.c:171
#define NROWSTOOSMALL
Definition: sepa_cgmip.c:155
#define DEFAULT_DYNAMICCUTS
Definition: sepa_cgmip.c:137
#define DEFAULT_MINNODELIMIT
Definition: sepa_cgmip.c:121
#define DEFAULT_CONTCONVERT
Definition: sepa_cgmip.c:127
static SCIP_RETCODE computeCut(SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Bool usefrac, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, SCIP_Bool *localrowsused, SCIP_Bool *localboundsused, int *cutrank, SCIP_Bool *success)
Definition: sepa_cgmip.c:2743
#define DEFAULT_USEOBJLB
Definition: sepa_cgmip.c:148
#define POSTPROCESS
Definition: sepa_cgmip.c:169
#define SEPA_DESC
Definition: sepa_cgmip.c:107
static SCIP_RETCODE createCGCutDirect(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
Definition: sepa_cgmip.c:3260
static SCIP_DECL_SEPACOPY(sepaCopyCGMIP)
Definition: sepa_cgmip.c:4278
static SCIP_DECL_CONSENFOLP(consEnfolpViolatedCuts)
Definition: sepa_cgmip.c:525
CGMIP_ColType
Definition: sepa_cgmip.c:228
@ colConverted
Definition: sepa_cgmip.c:231
@ colContinuous
Definition: sepa_cgmip.c:230
@ colPresent
Definition: sepa_cgmip.c:229
@ colAtUb
Definition: sepa_cgmip.c:232
@ colAtLb
Definition: sepa_cgmip.c:233
#define MAKECONTINTEGRAL
Definition: sepa_cgmip.c:173
#define NCOLSTOOSMALL
Definition: sepa_cgmip.c:156
#define DEFAULT_ONLYINTVARS
Definition: sepa_cgmip.c:126
#define DEFAULT_DECISIONTREE
Definition: sepa_cgmip.c:117
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_cgmip.c:115
#define SEPA_USESSUBSCIP
Definition: sepa_cgmip.c:111
#define DEFAULT_GENPRIMALSOLS
Definition: sepa_cgmip.c:152
#define DEFAULT_MAXDEPTH
Definition: sepa_cgmip.c:116
static SCIP_DECL_SEPAINIT(sepaInitCGMIP)
Definition: sepa_cgmip.c:4249
static SCIP_Real computeObjWeightSize(int rowsize, int minrowsize, int maxrowsize)
Definition: sepa_cgmip.c:888
static SCIP_RETCODE createCGCutStrongCG(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
Definition: sepa_cgmip.c:3773
#define DEFAULT_ONLYRANKONE
Definition: sepa_cgmip.c:125
#define DEFAULT_INTCONVERT
Definition: sepa_cgmip.c:130
#define FIXINTEGRALRHS
Definition: sepa_cgmip.c:172
#define DEFAULT_CMIROWNBOUNDS
Definition: sepa_cgmip.c:140
#define DEFAULT_OUTPUT
Definition: sepa_cgmip.c:150
#define DEFAULT_OBJLONE
Definition: sepa_cgmip.c:134
static SCIP_DECL_CONSLOCK(consLockViolatedCuts)
Definition: sepa_cgmip.c:592
static SCIP_RETCODE createCGMIPprimalsols(SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:2194
#define DEFAULT_EARLYTERM
Definition: sepa_cgmip.c:143
#define CONSHDLRFULLNORM
Definition: sepa_cgmip.c:161
struct CGMIP_MIPData CGMIP_MIPDATA
Definition: sepa_cgmip.c:273
#define USEVBDS
Definition: sepa_cgmip.c:168
static SCIP_RETCODE SCIPincludeConshdlrViolatedCut(SCIP *scip, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:601
#define DEFAULT_PRIMALSEPARATION
Definition: sepa_cgmip.c:142
static SCIP_RETCODE freeSubscip(SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:4158
#define SEPA_MAXBOUNDDIST
Definition: sepa_cgmip.c:110
#define DEFAULT_CONTCONVMIN
Definition: sepa_cgmip.c:129
#define MAXNSOLS
Definition: sepa_cgmip.c:163
#define BETAEPSILONVALUE
Definition: sepa_cgmip.c:159
static SCIP_DECL_CONSENFOPS(consEnfopsViolatedCuts)
Definition: sepa_cgmip.c:552
#define SEPA_FREQ
Definition: sepa_cgmip.c:109
#define MAXWEIGHTRANGE
Definition: sepa_cgmip.c:174
static SCIP_DECL_SEPAEXECLP(sepaExeclpCGMIP)
Definition: sepa_cgmip.c:4315
static SCIP_DECL_SEPAEXIT(sepaExitCGMIP)
Definition: sepa_cgmip.c:4264
#define MINFRAC
Definition: sepa_cgmip.c:170
#define DEFAULT_USEOBJUB
Definition: sepa_cgmip.c:147
#define DEFAULT_RANDSEED
Definition: sepa_cgmip.c:151
#define MAXAGGRLEN(nvars)
Definition: sepa_cgmip.c:178
#define DEFAULT_OBJWEIGHTSIZE
Definition: sepa_cgmip.c:136
static SCIP_DECL_CONSCHECK(consCheckViolatedCuts)
Definition: sepa_cgmip.c:566
static SCIP_RETCODE storeCutInArrays(SCIP *scip, int nvars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, int *cutinds, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
Definition: sepa_cgmip.c:637
#define SEPA_NAME
Definition: sepa_cgmip.c:106
static SCIP_DECL_CONSFREE(consFreeViolatedCuts)
Definition: sepa_cgmip.c:508
static SCIP_RETCODE transformColumn(SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_COL *col, SCIP_Real offset, SCIP_Real sigma, SCIP_Real *lhs, SCIP_Real *rhs, SCIP_Real *lb, SCIP_Real *ub, SCIP_Real *primsol)
Definition: sepa_cgmip.c:777
#define DEFAULT_ONLYACTIVEROWS
Definition: sepa_cgmip.c:123
static SCIP_RETCODE subscipSetParams(SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:2050
#define AWAY
Definition: sepa_cgmip.c:175
#define DEFAULT_MAXROUNDS
Definition: sepa_cgmip.c:114
#define DEFAULT_MEMORYLIMIT
Definition: sepa_cgmip.c:119
#define DEFAULT_MAXROWAGE
Definition: sepa_cgmip.c:124
#define DEFAULT_USECMIR
Definition: sepa_cgmip.c:138
#define OBJWEIGHTRANGE
Definition: sepa_cgmip.c:164
#define CONSHDLR_NAME
Definition: sepa_cgmip.c:281
static SCIP_RETCODE solCutIsViolated(SCIP *scip, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Bool *violated)
Definition: sepa_cgmip.c:309
#define DEFAULT_SUBSCIPFAST
Definition: sepa_cgmip.c:149
#define MINEFFICACY
Definition: sepa_cgmip.c:162
#define STALLNODELIMIT
Definition: sepa_cgmip.c:160
#define DEFAULT_MAXNODELIMIT
Definition: sepa_cgmip.c:122
#define DEFAULT_CONTCONVFRAC
Definition: sepa_cgmip.c:128
static SCIP_RETCODE createCGCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *cutoff, unsigned int *ngen)
Definition: sepa_cgmip.c:4004
#define DEFAULT_INTCONVFRAC
Definition: sepa_cgmip.c:131
enum CGMIP_ColType CGMIP_COLTYPE
Definition: sepa_cgmip.c:235
static SCIP_DECL_SEPAFREE(sepaFreeCGMIP)
Definition: sepa_cgmip.c:4293
#define DEFAULT_TIMELIMIT
Definition: sepa_cgmip.c:118
#define DEFAULT_USESTRONGCG
Definition: sepa_cgmip.c:139
Chvatal-Gomory cuts computed via a sub-MIP.
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_BASESTAT_UPPER
Definition: type_lpi.h:93
@ SCIP_BASESTAT_LOWER
Definition: type_lpi.h:91
enum SCIP_BaseStat SCIP_BASESTAT
Definition: type_lpi.h:96
@ SCIP_VERBLEVEL_NORMAL
Definition: type_message.h:55
@ SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:62
@ SCIP_PARAMEMPHASIS_FEASIBILITY
Definition: type_paramset.h:74
@ SCIP_OBJSENSE_MAXIMIZE
Definition: type_prob.h:47
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_FEASIBLE
Definition: type_result.h:45
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SEPARATED
Definition: type_result.h:49
@ SCIP_INFEASIBLE
Definition: type_result.h:46
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_ERROR
Definition: type_retcode.h:43
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52
@ SCIP_STAGE_SOLVED
Definition: type_set.h:54
@ SCIP_STAGE_SOLVING
Definition: type_set.h:53
enum SCIP_Stage SCIP_STAGE
Definition: type_set.h:59
@ SCIP_STATUS_OPTIMAL
Definition: type_stat.h:61
@ SCIP_STATUS_BESTSOLLIMIT
Definition: type_stat.h:57
@ SCIP_STATUS_USERINTERRUPT
Definition: type_stat.h:43
@ SCIP_STATUS_INFORUNBD
Definition: type_stat.h:64
@ SCIP_STATUS_STALLNODELIMIT
Definition: type_stat.h:48
@ SCIP_STATUS_TIMELIMIT
Definition: type_stat.h:51
@ SCIP_STATUS_INFEASIBLE
Definition: type_stat.h:62
@ SCIP_STATUS_NODELIMIT
Definition: type_stat.h:44
@ SCIP_STATUS_MEMLIMIT
Definition: type_stat.h:52
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:67
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51