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