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