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