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