Scippy

SCIP

Solving Constraint Integer Programs

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