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