Scippy

SCIP

Solving Constraint Integer Programs

sepa_cgmip.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
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 #ifndef NDEBUG
1068  unsigned int ncontconverted = 0;
1069  unsigned int nintconverted = 0;
1070 #endif
1071  unsigned int nlbounds;
1072  unsigned int nubounds;
1073 
1074  SCIP_VAR** consvars;
1075  SCIP_Real* consvals;
1076  SCIP_CONS* cons;
1077  int nconsvars;
1078  char name[SCIP_MAXSTRLEN];
1079 
1080  int ncols;
1081  int nrows;
1082  int ntotalrows;
1083  int maxrowsize = 0;
1084  int minrowsize = INT_MAX;
1085  int i, j;
1086 
1087  assert( origscip != NULL );
1088  assert( sepadata != NULL );
1089 
1090  assert( mipdata->subscip == NULL );
1091 
1092  SCIP_CALL( SCIPgetLPColsData(origscip, &cols, &ncols) );
1093  SCIP_CALL( SCIPgetLPRowsData(origscip, &rows, &nrows) );
1094  assert( ncols > 0 && nrows > 0 );
1095 
1096  mipdata->m = 0;
1097  mipdata->n = 0;
1098  mipdata->nrows = (unsigned int) nrows;
1099  mipdata->ncols = (unsigned int) ncols;
1100  mipdata->ntotalrows = mipdata->nrows;
1101 
1102  if ( sepadata->useobjub || sepadata->useobjlb )
1103  mipdata->ntotalrows = mipdata->nrows + 1;
1104 
1105  assert(mipdata->ntotalrows <= INT_MAX);
1106  ntotalrows = (int) mipdata->ntotalrows;
1107 
1108  /* copy value */
1109  mipdata->conshdlrusenorm = sepadata->conshdlrusenorm;
1110 
1111  /* create subscip */
1112  SCIP_CALL( SCIPcreate( &(mipdata->subscip) ) );
1113  subscip = mipdata->subscip;
1114  SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
1115 
1116  /* add violation constraint handler if requested */
1117  if ( sepadata->addviolconshdlr )
1118  {
1119  SCIP_CALL( SCIPincludeConshdlrViolatedCut(subscip, mipdata) );
1120  }
1121 
1122  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sepa_cgmip separating MIP (%s)", SCIPgetProbName(origscip));
1123  SCIP_CALL( SCIPcreateProb(subscip, name, NULL, NULL , NULL , NULL , NULL , NULL , NULL) );
1124  SCIPsetSubscipDepth(subscip, SCIPgetSubscipDepth(origscip) + 1);
1125  SCIP_CALL( SCIPsetObjsense(subscip, SCIP_OBJSENSE_MAXIMIZE) );
1126 
1127  /* alloc memory for subscipdata elements */
1128  SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->alpha), ncols) );
1129  SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->fracalpha), ncols) );
1130  SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->coltype), ncols) );
1131  SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->iscomplemented), ncols) );
1132  SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->isshifted), ncols) );
1133  SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->ylhs), ntotalrows) );
1134  SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->yrhs), ntotalrows) );
1135  SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->z), 2*ncols) );
1136  SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->lhs), ntotalrows) );
1137  SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->rhs), ntotalrows) );
1138  lhs = mipdata->lhs;
1139  rhs = mipdata->rhs;
1140 
1141  /* get temporary storage */
1142  SCIP_CALL( SCIPallocBufferArray(origscip, &lb, ncols) );
1143  SCIP_CALL( SCIPallocBufferArray(origscip, &ub, ncols) );
1144  SCIP_CALL( SCIPallocBufferArray(origscip, &primsol, ncols) );
1145 
1146  /* store lhs/rhs for complementing (see below) and compute maximal nonzeros of candidate rows */
1147  for (i = 0; i < nrows; ++i)
1148  {
1149  SCIP_Real val;
1150  SCIP_ROW* row;
1151 
1152  row = rows[i];
1153  assert( row != NULL );
1154 
1155  val = SCIProwGetLhs(row) - SCIProwGetConstant(row);
1156  if ( SCIProwIsIntegral(row) )
1157  val = SCIPfeasCeil(origscip, val); /* row is integral: round left hand side up */
1158  lhs[i] = val;
1159 
1160  val = SCIProwGetRhs(row) - SCIProwGetConstant(row);
1161  if ( SCIProwIsIntegral(row) )
1162  val = SCIPfeasFloor(origscip, val); /* row is integral: round right hand side down */
1163  rhs[i] = val;
1164 
1165  /* skip modifiable rows and local rows, unless allowed */
1166  if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1167  continue;
1168 
1169  /* skip rows that not have been active for a longer time */
1170  if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 && SCIProwGetAge(row) > sepadata->maxrowage )
1171  continue;
1172 
1173  /* check whether we want to skip cuts produced by the CGMIP separator */
1174  if ( sepadata->onlyrankone )
1175  {
1176  if ( SCIProwGetOriginSepa(row) == sepa )
1177  continue;
1178  }
1179 
1180  /* determine maximal row size: */
1181  val = SCIPgetRowLPActivity(origscip, row);
1182  if ( ! SCIPisInfinity(origscip, REALABS(lhs[i])) )
1183  {
1184  if ( ! sepadata->onlyactiverows || SCIPisFeasEQ(origscip, val, SCIProwGetLhs(row)) )
1185  {
1186  if ( SCIProwGetNLPNonz(row) > maxrowsize )
1187  maxrowsize = SCIProwGetNLPNonz(row);
1188  if ( SCIProwGetNLPNonz(row) < minrowsize )
1189  minrowsize = SCIProwGetNLPNonz(row);
1190  }
1191  }
1192  else
1193  {
1194  if ( ! SCIPisInfinity(origscip, rhs[i]) )
1195  {
1196  if ( ! sepadata->onlyactiverows || SCIPisFeasEQ(origscip, val, SCIProwGetRhs(row)) )
1197  {
1198  if ( SCIProwGetNLPNonz(row) > maxrowsize )
1199  maxrowsize = SCIProwGetNLPNonz(row);
1200  if ( SCIProwGetNLPNonz(row) < minrowsize )
1201  minrowsize = SCIProwGetNLPNonz(row);
1202  }
1203  }
1204  }
1205  }
1206  assert( maxrowsize > 0 );
1207  assert( minrowsize < INT_MAX );
1208 
1209  /* add cuts for objective function if required */
1210  if ( sepadata->useobjub )
1211  {
1212  assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1213  rhs[mipdata->nrows] = SCIPgetUpperbound(origscip);
1214  assert( ! SCIPisObjIntegral(origscip) || SCIPisFeasIntegral(origscip, SCIPgetUpperbound(origscip)) );
1215 
1216  if ( ! SCIPisInfinity(origscip, SCIPgetUpperbound(origscip)) && SCIPgetNObjVars(origscip) > maxrowsize )
1217  maxrowsize = SCIPgetNObjVars(origscip);
1218  if ( ! SCIPisInfinity(origscip, SCIPgetUpperbound(origscip)) && SCIPgetNObjVars(origscip) < minrowsize )
1219  minrowsize = SCIPgetNObjVars(origscip);
1220  }
1221  if ( sepadata->useobjlb )
1222  {
1223  assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1224 
1225  if ( SCIPisObjIntegral(origscip) )
1226  lhs[mipdata->nrows] = SCIPfeasCeil(origscip, SCIPgetLowerbound(origscip));
1227  else
1228  lhs[mipdata->nrows] = SCIPgetLowerbound(origscip);
1229 
1230  if ( ! SCIPisInfinity(origscip, -SCIPgetLowerbound(origscip)) && SCIPgetNObjVars(origscip) > maxrowsize )
1231  maxrowsize = SCIPgetNObjVars(origscip);
1232  if ( ! SCIPisInfinity(origscip, -SCIPgetLowerbound(origscip)) && SCIPgetNObjVars(origscip) < minrowsize )
1233  minrowsize = SCIPgetNObjVars(origscip);
1234  }
1235 
1236  /* store lb/ub for complementing and perform preprocessing */
1237  nshifted = 0;
1238  ncomplemented = 0;
1239  nlbounds = 0;
1240  nubounds = 0;
1241  for (j = 0; j < ncols; ++j)
1242  {
1243  SCIP_COL* col;
1244  SCIP_VAR* var;
1245 
1246  col = cols[j];
1247  assert( col != NULL );
1248  var = SCIPcolGetVar(col);
1249  assert( var != NULL );
1250 
1251  primsol[j] = SCIPcolGetPrimsol(col);
1252  assert( SCIPisEQ(origscip, SCIPgetVarSol(origscip, var), primsol[j]) );
1253 
1254  lb[j] = SCIPvarGetLbGlobal(var);
1255  assert( SCIPisEQ(origscip, SCIPvarGetLbLocal(var), SCIPcolGetLb(col)) );
1256 
1257  /* if allowed, try to use stronger local bound */
1258  if ( sepadata->allowlocal && SCIPisGT(origscip, SCIPvarGetLbLocal(var), lb[j]) )
1259  lb[j] = SCIPvarGetLbLocal(var);
1260 
1261  ub[j] = SCIPvarGetUbGlobal(var);
1262  assert( SCIPisEQ(origscip, SCIPvarGetUbLocal(var), SCIPcolGetUb(col)) );
1263 
1264  /* if allowed, try to use stronger local bound */
1265  if ( sepadata->allowlocal && SCIPisLT(origscip, SCIPvarGetUbLocal(var), ub[j]) )
1266  ub[j] = SCIPvarGetUbLocal(var);
1267 
1268  mipdata->coltype[j] = colPresent;
1269  mipdata->iscomplemented[j] = FALSE;
1270  mipdata->isshifted[j] = FALSE;
1271 
1272  /* check status of column/variable */
1273  if ( SCIPcolIsIntegral(col) )
1274  {
1275  /* integral variables taking integral values are not interesting - will be substituted out below */
1276  if ( ! SCIPisFeasIntegral(origscip, primsol[j]) )
1277  {
1278  /* possibly convert fractional integral variables to take integral values */
1279  if ( sepadata->intconvert && ncols >= sepadata->intconvmin )
1280  {
1281  /* randomly convert variables */
1282  if ( SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->intconvfrac )
1283  {
1284  assert( ! SCIPisInfinity(origscip, ub[j]) || ! SCIPisInfinity(origscip, -lb[j]) );
1285 
1286  /* if both bounds are finite, take the closer one */
1287  if ( ! SCIPisInfinity(origscip, ub[j]) && ! SCIPisInfinity(origscip, -lb[j]) )
1288  {
1289  assert( SCIPisFeasIntegral(origscip, ub[j]) );
1290  assert( SCIPisFeasIntegral(origscip, lb[j]) );
1291  assert( SCIPisFeasLT(origscip, primsol[j], ub[j]) );
1292  assert( SCIPisFeasGT(origscip, primsol[j], lb[j]) );
1293  if ( ub[j] - primsol[j] < primsol[j] - lb[j] )
1294  primsol[j] = ub[j];
1295  else
1296  primsol[j] = lb[j];
1297 #ifndef NDEBUG
1298  ++nintconverted;
1299 #endif
1300  }
1301  else
1302  {
1303  /* if only lower bound is finite */
1304  if ( ! SCIPisInfinity(origscip, -lb[j]) )
1305  {
1306  assert( SCIPisFeasIntegral(origscip, lb[j]) );
1307  primsol[j] = lb[j];
1308 #ifndef NDEBUG
1309  ++nintconverted;
1310 #endif
1311  }
1312  else
1313  {
1314  assert( ! SCIPisInfinity(origscip, ub[j]) );
1315  assert( SCIPisFeasIntegral(origscip, ub[j]) );
1316  primsol[j] = ub[j];
1317 #ifndef NDEBUG
1318  ++nintconverted;
1319 #endif
1320  }
1321  }
1322  }
1323  }
1324  }
1325 
1326  /* integral variables taking integral values are not interesting - will be substituted out below */
1327  if ( ! SCIPisFeasIntegral(origscip, primsol[j]) )
1328  {
1329  /* possibly convert integral variables to be continuous */
1330  if ( sepadata->contconvert && ncols >= sepadata->contconvmin )
1331  {
1332  /* randomly convert variables */
1333  if ( SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->contconvfrac )
1334  {
1335  /* preprocessing is also performed for converted columns */
1336  mipdata->coltype[j] = colConverted;
1337 #ifndef NDEBUG
1338  ++ncontconverted;
1339 #endif
1340  }
1341  }
1342  }
1343  }
1344  else
1345  {
1346  /* detect continuous variables, but perform preprocessing for them */
1347  mipdata->coltype[j] = colContinuous;
1348  }
1349 
1350  /* if integer variable is at its upper bound -> complementing (this also generates a 0 lower bound) */
1351  if ( mipdata->coltype[j] == colPresent && SCIPisFeasEQ(origscip, primsol[j], ub[j]) )
1352  {
1353  assert( ! SCIPisInfinity(origscip, ub[j]) );
1354  SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1355  mipdata->iscomplemented[j] = TRUE;
1356  mipdata->coltype[j] = colAtUb;
1357  ++nubounds;
1358  }
1359  else
1360  {
1361  /* if a variable has a finite nonzero lower bound -> shift */
1362  if ( ! SCIPisInfinity(origscip, -lb[j]) )
1363  {
1364  if ( ! SCIPisZero(origscip, lb[j]) )
1365  {
1366  SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, -lb[j], 1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1367  assert( SCIPisZero(origscip, lb[j]) );
1368  mipdata->isshifted[j] = TRUE;
1369  ++nshifted;
1370  }
1371 
1372  /* if integer variable is at its lower bound */
1373  if ( mipdata->coltype[j] == colPresent && SCIPisZero(origscip, primsol[j]) )
1374  {
1375  mipdata->coltype[j] = colAtLb;
1376  ++nlbounds;
1377  }
1378  }
1379  else
1380  {
1381  /* lower bound is minus-infinity -> check whether upper bound is finite */
1382  if ( ! SCIPisInfinity(origscip, ub[j]) )
1383  {
1384  /* complement variable */
1385  SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1386  assert( SCIPisZero(origscip, lb[j]) );
1387  mipdata->iscomplemented[j] = TRUE;
1388  ++ncomplemented;
1389 
1390  /* if integer variable is at its lower bound */
1391  if ( mipdata->coltype[j] == colPresent && SCIPisZero(origscip, primsol[j]) )
1392  {
1393  mipdata->coltype[j] = colAtLb;
1394  ++nlbounds;
1395  }
1396  }
1397  }
1398  }
1399 
1400  assert( SCIPisFeasLE(origscip, lb[j], primsol[j]) );
1401  assert( SCIPisFeasLE(origscip, primsol[j], ub[j]) );
1402  }
1403 
1404 #ifndef NDEBUG
1405  if ( sepadata->intconvert && ncols >= sepadata->intconvmin )
1406  {
1407  SCIPdebugMsg(origscip, "Converted %u fractional integral variables to have integral value.\n", nintconverted);
1408  }
1409  if ( sepadata->contconvert && ncols >= sepadata->contconvmin )
1410  {
1411  SCIPdebugMsg(origscip, "Converted %u integral variables to be continuous.\n", ncontconverted);
1412  }
1413 #endif
1414  SCIPdebugMsg(origscip, "Original variables: %d integral, %d continuous, %u shifted, %u complemented, %u at lb, %u at ub\n",
1415  SCIPgetNBinVars(origscip) + SCIPgetNIntVars(origscip) + SCIPgetNImplVars(origscip), SCIPgetNContVars(origscip),
1416  nshifted, ncomplemented, nlbounds, nubounds);
1417 
1418  /* prepare upper bound on y-variables */
1419  if ( sepadata->skipmultbounds )
1420  multvarub = SCIPinfinity(origscip);
1421  else
1422  multvarub = 1.0 - EPSILONVALUE;
1423 
1424  /* create artificial variables for row combinations (y-variables) */
1425  cnt = 0;
1426  for (i = 0; i < nrows; ++i)
1427  {
1428  SCIP_ROW* row;
1429 
1430  row = rows[i];
1431  assert( row != NULL );
1432 
1433  mipdata->ylhs[i] = NULL;
1434  mipdata->yrhs[i] = NULL;
1435 
1436  /* skip modifiable rows and local rows, unless allowed */
1437  if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1438  continue;
1439 
1440  /* skip rows that not have been active for a longer time */
1441  if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 && SCIProwGetAge(row) > sepadata->maxrowage )
1442  continue;
1443 
1444  /* check whether we want to skip cuts produced by the CGMIP separator */
1445  if ( sepadata->onlyrankone )
1446  {
1447  if ( SCIProwGetOriginSepa(row) == sepa )
1448  continue;
1449  }
1450 
1451  /* if we have an equation */
1452  if ( SCIPisEQ(origscip, lhs[i], rhs[i]) )
1453  {
1454  SCIP_Real weight = -sepadata->objweight;
1455 
1456  assert( ! SCIPisInfinity(origscip, rhs[i]) );
1457  assert( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetLhs(row)) ); /* equations should always be active */
1458  assert( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetRhs(row)) );
1459 
1460  if ( sepadata->objweightsize )
1461  weight = - sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
1462 
1463  /* create two variables for each equation */
1464  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yeq1_%d", i);
1465  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[i]), name, 0.0, multvarub,
1466  weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1467  SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[i]) );
1468  ++cnt;
1469 
1470 #ifdef SCIP_MORE_DEBUG
1471  SCIPdebugMsg(origscip, "Created variable <%s> for equation <%s>.\n", name, SCIProwGetName(row));
1472 #endif
1473 
1474  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yeq2_%d", i);
1475  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[i]), name, 0.0, multvarub,
1476  weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1477  SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[i]) );
1478  ++cnt;
1479 
1480 #ifdef SCIP_MORE_DEBUG
1481  SCIPdebugMsg(origscip, "Created variable <%s> for equation <%s>.\n", name, SCIProwGetName(row));
1482 #endif
1483  }
1484  else
1485  {
1486  /* create variable for lhs of row if necessary */
1487  if ( ! SCIPisInfinity(origscip, -lhs[i]) )
1488  {
1489  SCIP_Bool isactive = FALSE;
1490  SCIP_Real weight = 0.0;
1491 
1492  /* if the row is active, use objective weight equal to -sepadata->objweight */
1493  if ( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetLhs(row)) )
1494  {
1495  isactive = TRUE;
1496  if ( sepadata->objweightsize )
1497  weight = -sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
1498  else
1499  weight = -sepadata->objweight;
1500  }
1501 
1502  if ( ! sepadata->onlyactiverows || isactive )
1503  {
1504  /* add variable */
1505  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ylhs_%d", i);
1506  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[i]), name, 0.0, multvarub,
1507  weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1508  SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[i]) );
1509  ++cnt;
1510 
1511 #ifdef SCIP_MORE_DEBUG
1512  SCIPdebugMsg(origscip, "Created variable <%s> for >= inequality <%s> (weight: %f).\n", name, SCIProwGetName(row), weight);
1513 #endif
1514  }
1515  }
1516 
1517  /* create variable for rhs of row if necessary */
1518  if ( ! SCIPisInfinity(origscip, rhs[i]) )
1519  {
1520  SCIP_Bool isactive = FALSE;
1521  SCIP_Real weight = 0.0;
1522 
1523  /* if the row is active, use objective weight equal to -sepadata->objweight */
1524  if ( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetRhs(row)) )
1525  {
1526  isactive = TRUE;
1527  if ( sepadata->objweightsize )
1528  weight = -sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
1529  else
1530  weight = -sepadata->objweight;
1531  }
1532 
1533  if ( ! sepadata->onlyactiverows || isactive )
1534  {
1535  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yrhs_%d", i);
1536  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[i]), name, 0.0, multvarub,
1537  weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1538  SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[i]) );
1539  ++cnt;
1540 
1541 #ifdef SCIP_MORE_DEBUG
1542  SCIPdebugMsg(origscip, "Created variable <%s> for <= inequality <%s> (weight: %f).\n", name, SCIProwGetName(row), weight);
1543 #endif
1544  }
1545  }
1546  }
1547  }
1548  assert( (int) cnt <= 2 * nrows );
1549  mipdata->n += cnt;
1550 
1551  /* create artificial variables for objective function (if required) (y-variables) */
1552  if ( sepadata->useobjub || sepadata->useobjlb )
1553  {
1554  SCIP_Real weight = 0.0;
1555 
1556  assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1557  mipdata->ylhs[mipdata->nrows] = NULL;
1558  mipdata->yrhs[mipdata->nrows] = NULL;
1559  cnt = 0;
1560 
1561  if ( sepadata->objweightsize )
1562  weight = -sepadata->objweight * computeObjWeightSize(SCIPgetNObjVars(origscip), minrowsize, maxrowsize);
1563  else
1564  weight = -sepadata->objweight;
1565 
1566  /* create variable for upper objective bound if necessary */
1567  if ( sepadata->useobjub && ! SCIPisInfinity(origscip, rhs[mipdata->nrows]) )
1568  {
1569  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yobjub");
1570  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[mipdata->nrows]), name, 0.0, multvarub,
1571  weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1572  SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[mipdata->nrows]) );
1573  ++cnt;
1574 
1575 #ifdef SCIP_MORE_DEBUG
1576  SCIPdebugMsg(origscip, "Created variable <%s> for upper bound on objective (weight: %f).\n", name, weight);
1577 #endif
1578  }
1579 
1580  /* create variable for lower bound objective if necessary */
1581  if ( sepadata->useobjlb && ! SCIPisInfinity(origscip, -lhs[mipdata->nrows]) )
1582  {
1583  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yobjlb");
1584  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[mipdata->nrows]), name, 0.0, multvarub,
1585  weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1586  SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[mipdata->nrows]) );
1587  ++cnt;
1588 
1589 #ifdef SCIP_MORE_DEBUG
1590  SCIPdebugMsg(origscip, "Created variable <%s> for lower bound on objective (weight: %f).\n", name, weight);
1591 #endif
1592  }
1593 
1594  assert( (int) cnt <= 2 * ntotalrows );
1595  mipdata->n += cnt;
1596  }
1597 
1598  /* create alpha, bound, and fractional variables */
1599  cnt = 0;
1600  ucnt = 0;
1601  for (j = 0; j < ncols; ++j)
1602  {
1603  mipdata->z[j] = NULL;
1604  mipdata->alpha[j] = NULL;
1605  mipdata->fracalpha[j] = NULL;
1606 
1607  if ( mipdata->coltype[j] == colPresent )
1608  {
1609  SCIP_Real obj;
1610 
1611  if ( sepadata->objlone )
1612  obj = 0.0;
1613  else
1614  obj = primsol[j];
1615 
1616  /* create alpha variables */
1617  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "alpha_%d", j);
1618  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->alpha[j]), name, -sepadata->cutcoefbnd, sepadata->cutcoefbnd, obj,
1619  SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1620  SCIP_CALL( SCIPaddVar(subscip, mipdata->alpha[j]) );
1621  ++cnt;
1622 
1623  /* create fractional variables */
1624  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "f_%d", j);
1625  if ( SCIPisInfinity(origscip, -lb[j]) && SCIPisInfinity(origscip, ub[j]) )
1626  {
1627  /* fix fractional value to be zero for free original variables */
1628  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracalpha[j]), name, 0.0, 0.0, 0.0,
1629  SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1630  }
1631  else
1632  {
1633  /* fractional value in [0, 1) for variables with finite bounds */
1634  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracalpha[j]), name, 0.0, 1.0-EPSILONVALUE, 0.0,
1635  SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1636  }
1637  SCIP_CALL( SCIPaddVar(subscip, mipdata->fracalpha[j]) );
1638  ++cnt;
1639 
1640  /* create variables for upper bounds */
1641  if ( ! SCIPisInfinity(origscip, ub[j]) )
1642  {
1643  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "zub_%d", j);
1644  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->z[j]), name, 0.0, multvarub,
1645  0.0, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1646  SCIP_CALL( SCIPaddVar(subscip, mipdata->z[j]) );
1647  ++ucnt;
1648  }
1649  }
1650  }
1651  assert( (int) cnt <= 2 * ncols );
1652  assert( (int) ucnt <= ncols );
1653 
1654  /* create variable for the rhs of the cut */
1655  if ( sepadata->objlone )
1656  {
1657  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, 0.0,
1658  SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1659  }
1660  else
1661  {
1662  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, -1.0,
1663  SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1664  }
1665  SCIP_CALL( SCIPaddVar(subscip, mipdata->beta) );
1666 
1667  /* create fractional variable for the rhs */
1668  SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracbeta), "fracbeta", 0.0, 1.0-BETAEPSILONVALUE, 0.0,
1669  SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1670  SCIP_CALL( SCIPaddVar(subscip, mipdata->fracbeta) );
1671  mipdata->n += cnt + ucnt + 2;
1672 
1673  /* get temporary storage */
1674  SCIP_CALL( SCIPallocBufferArray(origscip, &consvals, (int) mipdata->n) );
1675  SCIP_CALL( SCIPallocBufferArray(origscip, &consvars, (int) mipdata->n) );
1676 
1677  /* create constraints for alpha variables of CG-cut */
1678  cnt = 0;
1679  for (j = 0; j < ncols; ++j)
1680  {
1681  SCIP_ROW** colrows;
1682  SCIP_Real* colvals;
1683 
1684  /* create ordinary part for all selected variables */
1685  if ( mipdata->coltype[j] == colPresent )
1686  {
1687  SCIP_Real sigma;
1688 
1689  assert( cols[j] != NULL );
1690  colrows = SCIPcolGetRows(cols[j]);
1691  colvals = SCIPcolGetVals(cols[j]);
1692  nconsvars = 0;
1693 
1694  if ( mipdata->iscomplemented[j] )
1695  sigma = -1.0;
1696  else
1697  sigma = 1.0;
1698 
1699  /* add part for columns */
1700  for (i = 0; i < SCIPcolGetNLPNonz(cols[j]); ++i)
1701  {
1702  SCIP_ROW* row;
1703  int pos;
1704 
1705  row = colrows[i];
1706  assert( row != NULL );
1707 
1708  /* skip modifiable rows and local rows, unless allowed */
1709  if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1710  continue;
1711 
1712  pos = SCIProwGetLPPos(row);
1713  assert( 0 <= pos && pos < nrows );
1714 
1715  if ( mipdata->ylhs[pos] != NULL )
1716  {
1717  consvars[nconsvars] = mipdata->ylhs[pos];
1718  consvals[nconsvars] = -sigma * colvals[i];
1719  ++nconsvars;
1720  }
1721  if ( mipdata->yrhs[pos] != NULL )
1722  {
1723  consvars[nconsvars] = mipdata->yrhs[pos];
1724  consvals[nconsvars] = sigma * colvals[i];
1725  ++nconsvars;
1726  }
1727  assert( nconsvars <= (int) mipdata->n );
1728  }
1729  /* add part for upper bounds */
1730  if ( mipdata->z[j] != NULL )
1731  {
1732  assert( ! SCIPisInfinity(origscip, ub[j]) );
1733  consvars[nconsvars] = mipdata->z[j];
1734  consvals[nconsvars] = 1.0;
1735  ++nconsvars;
1736  }
1737  assert( nconsvars <= (int) mipdata->n );
1738 
1739  /* add alpha variable */
1740  consvars[nconsvars] = mipdata->alpha[j];
1741  consvals[nconsvars] = -1.0;
1742  ++nconsvars;
1743  assert( nconsvars <= (int) mipdata->n );
1744 
1745  /* add fractional-alpha variable */
1746  consvars[nconsvars] = mipdata->fracalpha[j];
1747  consvals[nconsvars] = -1.0;
1748  ++nconsvars;
1749  assert( nconsvars <= (int) mipdata->n );
1750 
1751  /* check for lower and upper objective bounds */
1752  if ( (sepadata->useobjub || sepadata->useobjlb) && ! SCIPisZero(origscip, SCIPcolGetObj(cols[j])) )
1753  {
1754  /* add lower objective bound */
1755  if ( mipdata->ylhs[mipdata->nrows] != NULL )
1756  {
1757  assert( sepadata->useobjlb );
1758  consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1759  consvals[nconsvars] = -sigma * SCIPcolGetObj(cols[j]);
1760  ++nconsvars;
1761  }
1762 
1763  /* add upper objective bound */
1764  if ( mipdata->yrhs[mipdata->nrows] != NULL )
1765  {
1766  assert( sepadata->useobjub );
1767  consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1768  consvals[nconsvars] = sigma * SCIPcolGetObj(cols[j]);
1769  ++nconsvars;
1770  }
1771  }
1772 
1773  /* add linear constraint */
1774  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "alpha_%d", j);
1775  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, name, nconsvars, consvars, consvals, 0.0, 0.0,
1776  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1777  SCIP_CALL( SCIPaddCons(subscip, cons) );
1778  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1779  ++cnt;
1780  }
1781  /* generate part that makes sure that cut is valid for continuous variables */
1782  else if ( mipdata->coltype[j] == colContinuous || mipdata->coltype[j] == colConverted )
1783  {
1784  SCIP_Real sigma;
1785  SCIP_Real r;
1786 
1787  assert( cols[j] != NULL );
1788  colrows = SCIPcolGetRows(cols[j]);
1789  colvals = SCIPcolGetVals(cols[j]);
1790  nconsvars = 0;
1791 
1792  if ( mipdata->iscomplemented[j] )
1793  sigma = -1.0;
1794  else
1795  sigma = 1.0;
1796 
1797  /* add part for columns */
1798  for (i = 0; i < SCIPcolGetNLPNonz(cols[j]); ++i)
1799  {
1800  SCIP_ROW* row;
1801  int pos;
1802 
1803  row = colrows[i];
1804  assert( row != NULL );
1805 
1806  /* skip modifiable rows and local rows, unless allowed */
1807  if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1808  continue;
1809 
1810  pos = SCIProwGetLPPos(row);
1811  assert( 0 <= pos && pos < nrows );
1812 
1813  if ( mipdata->ylhs[pos] != NULL )
1814  {
1815  consvars[nconsvars] = mipdata->ylhs[pos];
1816  consvals[nconsvars] = -sigma * colvals[i];
1817  ++nconsvars;
1818  }
1819  if ( mipdata->yrhs[pos] != NULL )
1820  {
1821  consvars[nconsvars] = mipdata->yrhs[pos];
1822  consvals[nconsvars] = sigma * colvals[i];
1823  ++nconsvars;
1824  }
1825  assert( nconsvars <= (int) mipdata->n );
1826  }
1827 
1828  /* check for lower and upper objective bounds */
1829  if ( (sepadata->useobjub || sepadata->useobjlb) && ! SCIPisZero(origscip, SCIPcolGetObj(cols[j])) )
1830  {
1831  /* add lower objective bound */
1832  if ( mipdata->ylhs[mipdata->nrows] )
1833  {
1834  assert( sepadata->useobjlb );
1835  consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1836  consvals[nconsvars] = -sigma * SCIPcolGetObj(cols[j]);
1837  ++nconsvars;
1838  }
1839 
1840  /* add upper objective bound */
1841  if ( mipdata->yrhs[mipdata->nrows] )
1842  {
1843  assert( sepadata->useobjub );
1844  consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1845  consvals[nconsvars] = sigma * SCIPcolGetObj(cols[j]);
1846  ++nconsvars;
1847  }
1848  }
1849 
1850  /* add linear constraint */
1851  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cont_%d", j);
1852 
1853  /* for free continuous variables require equality */
1854  r = SCIPinfinity(subscip);
1855  if ( SCIPisInfinity(origscip, -lb[j]) && SCIPisInfinity(origscip, ub[j]) )
1856  r = 0.0;
1857  else
1858  assert( SCIPisZero(origscip, lb[j]) );
1859 
1860  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, name, nconsvars, consvars, consvals, 0.0, r,
1861  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1862  SCIP_CALL( SCIPaddCons(subscip, cons) );
1863  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1864  ++cnt;
1865  }
1866  }
1867  assert( (int) cnt <= ncols );
1868  mipdata->m += cnt;
1869 
1870  /* create constraints for rhs of cut */
1871  nconsvars = 0;
1872 
1873  /* first for the rows */
1874  for (i = 0; i < nrows; ++i)
1875  {
1876  assert( rows[i] != NULL );
1877 
1878  /* skip modifiable rows and local rows, unless allowed */
1879  if ( SCIProwIsModifiable(rows[i]) || (SCIProwIsLocal(rows[i]) && !sepadata->allowlocal) )
1880  continue;
1881 
1882  /* if lhs is there */
1883  if ( mipdata->ylhs[i] != NULL && ! SCIPisZero(origscip, lhs[i]) )
1884  {
1885  assert( ! SCIPisInfinity(origscip, -lhs[i]) );
1886  consvars[nconsvars] = mipdata->ylhs[i];
1887  consvals[nconsvars] = -lhs[i];
1888  ++nconsvars;
1889  }
1890  /* if rhs is there */
1891  if ( mipdata->yrhs[i] != NULL && ! SCIPisZero(origscip, rhs[i]) )
1892  {
1893  assert( ! SCIPisInfinity(origscip, rhs[i]) );
1894  consvars[nconsvars] = mipdata->yrhs[i];
1895  consvals[nconsvars] = rhs[i];
1896  ++nconsvars;
1897  }
1898  assert( nconsvars <= (int) mipdata->n );
1899  }
1900 
1901  if ( sepadata->useobjub || sepadata->useobjlb )
1902  {
1903  /* add lower objective bound */
1904  if ( mipdata->ylhs[mipdata->nrows] != NULL && ! SCIPisZero(origscip, lhs[mipdata->nrows]) )
1905  {
1906  assert( sepadata->useobjlb );
1907  assert( ! SCIPisInfinity(origscip, -lhs[mipdata->nrows]) );
1908  consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1909  consvals[nconsvars] = -lhs[mipdata->nrows];
1910  ++nconsvars;
1911  }
1912 
1913  /* add upper objective bound */
1914  if ( mipdata->yrhs[mipdata->nrows] != NULL && ! SCIPisZero(origscip, rhs[mipdata->nrows]) )
1915  {
1916  assert( sepadata->useobjub );
1917  assert( ! SCIPisInfinity(origscip, rhs[mipdata->nrows]) );
1918  consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1919  consvals[nconsvars] = rhs[mipdata->nrows];
1920  ++nconsvars;
1921  }
1922  assert( nconsvars <= (int) mipdata->n );
1923  }
1924 
1925  /* next for the columns */
1926  for (j = 0; j < ncols; ++j)
1927  {
1928  /* if ub is there */
1929  if ( mipdata->z[j] != NULL && ! SCIPisZero(origscip, ub[j]) )
1930  {
1931  assert( mipdata->coltype[j] == colPresent );
1932  assert( ! SCIPisInfinity(origscip, ub[j]) );
1933  consvars[nconsvars] = mipdata->z[j];
1934  consvals[nconsvars] = ub[j];
1935  ++nconsvars;
1936  assert( nconsvars <= (int) mipdata->n );
1937  }
1938  }
1939  /* add beta variable */
1940  consvars[nconsvars] = mipdata->beta;
1941  consvals[nconsvars] = -1.0;
1942  ++nconsvars;
1943 
1944  /* add fractional-beta variable */
1945  consvars[nconsvars] = mipdata->fracbeta;
1946  consvals[nconsvars] = -1.0;
1947  ++nconsvars;
1948  assert( nconsvars <= (int) mipdata->n );
1949 
1950  /* add linear constraint */
1951  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "beta", nconsvars, consvars, consvals, 0.0, 0.0,
1952  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1953  SCIP_CALL( SCIPaddCons(subscip, cons) );
1954  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1955  ++mipdata->m;
1956 
1957  /* add primal separation constraint if required */
1958  if ( sepadata->primalseparation )
1959  {
1960  SCIP_SOL* bestsol;
1961  bestsol = SCIPgetBestSol(origscip);
1962  if ( bestsol != NULL )
1963  {
1964  nconsvars = 0;
1965  for (j = 0; j < ncols; ++j)
1966  {
1967  if ( mipdata->alpha[j] != NULL )
1968  {
1969  SCIP_Real val;
1970  assert( mipdata->coltype[j] == colPresent );
1971 
1972  val = SCIPgetSolVal(origscip, bestsol, SCIPcolGetVar(cols[j]));
1973  consvars[nconsvars] = mipdata->alpha[j];
1974  consvals[nconsvars] = val;
1975  ++nconsvars;
1976  assert( nconsvars <= (int) mipdata->n );
1977  }
1978  }
1979  consvars[nconsvars] = mipdata->beta;
1980  consvals[nconsvars] = -1.0;
1981  ++nconsvars;
1982 
1983  /* add linear constraint - allow slight deviation from equality */
1984  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "primalseparation", nconsvars, consvars, consvals, -EPSILONVALUE, EPSILONVALUE,
1985  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1986  SCIP_CALL( SCIPaddCons(subscip, cons) );
1987  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1988  ++mipdata->m;
1989  }
1990  }
1991 
1992  /* add constraint to force violated cuts if required */
1993  if ( sepadata->addviolationcons )
1994  {
1995  nconsvars = 0;
1996  for (j = 0; j < ncols; ++j)
1997  {
1998  if ( mipdata->alpha[j] != NULL )
1999  {
2000  consvars[nconsvars] = mipdata->alpha[j];
2001  consvals[nconsvars] = primsol[j];
2002  ++nconsvars;
2003  assert( nconsvars <= (int) mipdata->n );
2004  }
2005  }
2006  consvars[nconsvars] = mipdata->beta;
2007  consvals[nconsvars] = -1.0;
2008  ++nconsvars;
2009 
2010  /* add linear constraint - allow slight deviation from equality */
2011  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "violationConstraint", nconsvars, consvars, consvals, MINEFFICACY, SCIPinfinity(subscip),
2012  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2013  SCIP_CALL( SCIPaddCons(subscip, cons) );
2014  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
2015  ++mipdata->m;
2016  }
2017 
2018  SCIPdebugMsg(origscip, "Subscip has %u vars (%d integral, %d continuous), %u conss.\n",
2019  mipdata->n, SCIPgetNIntVars(subscip), SCIPgetNContVars(subscip), mipdata->m);
2020 
2021  /* free temporary memory */
2022  SCIPfreeBufferArray(origscip, &consvars);
2023  SCIPfreeBufferArray(origscip, &consvals);
2024 
2025  SCIPfreeBufferArray(origscip, &primsol);
2026  SCIPfreeBufferArray(origscip, &lb);
2027  SCIPfreeBufferArray(origscip, &ub);
2028 
2029  /* SCIPdebug( SCIP_CALL( SCIPprintOrigProblem(subscip, NULL, NULL, FALSE) ) ); */
2030 
2031 #ifdef SCIP_WRITEPROB
2032  {
2033  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgsepa%s%s%s%s_%s.lp",
2034  sepadata->objlone ? "_l1" : "",
2035  sepadata->addviolationcons ? "_vc" : "",
2036  sepadata->skipmultbounds ? "_ub" : "",
2037  sepadata->primalseparation ? "_ps" : "",
2038  SCIPgetProbName(origscip));
2039  SCIP_CALL( SCIPwriteOrigProblem(subscip, name, "lp", FALSE) );
2040  SCIPinfoMessage(origscip, NULL, "Wrote subscip to file <%s>.\n", name);
2041  }
2042 #endif
2043 
2044  return SCIP_OKAY;
2045 }
2046 
2047 
2048 /** sets parameters for subscip */
2049 static
2050 SCIP_RETCODE subscipSetParams(
2051  SCIP_SEPADATA* sepadata, /**< separator data */
2052  CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
2053  )
2054 {
2055  SCIP* subscip;
2056 
2057  assert( sepadata != NULL );
2058  assert( mipdata != NULL );
2059 
2060  subscip = mipdata->subscip;
2061  assert( subscip != NULL );
2062 
2063  /* set objective limit, if no corresponding constraint has been added */
2064  if ( ! sepadata->addviolationcons && ! sepadata->addviolconshdlr )
2065  {
2066  SCIP_CALL( SCIPsetObjlimit(subscip, MINEFFICACY) );
2067  }
2068 
2069  /* do not abort subscip on CTRL-C */
2070  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
2071 
2072  /* disable memory saving mode: this is likely to result in the maximal depth being reached. This is because DFS
2073  * results in a repeated branching on the alpha-variables, which often have large bounds resulting in deep levels of
2074  * the tree. */
2075  SCIP_CALL( SCIPsetRealParam(subscip, "memory/savefac", 1.0) );
2076 
2077  /* set number of solutions stored */
2078  SCIP_CALL( SCIPsetIntParam(subscip, "limits/maxsol", MAXNSOLS) );
2079 
2080  /* determine output to console */
2081 #ifdef SCIP_OUTPUT
2082  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2083  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1000) );
2084  SCIP_CALL( SCIPsetIntParam(subscip, "display/nsols/active", 2) );
2085 #else
2086  if ( sepadata->output )
2087  {
2088  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2089  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1000) );
2090  SCIP_CALL( SCIPsetIntParam(subscip, "display/nsols/active", 2) );
2091  }
2092  else
2093  {
2094  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
2095  }
2096 #endif
2097 
2098  if ( sepadata->subscipfast )
2099  {
2100  /* forbid recursive call of plugins solving subMIPs (also disables CG-separation) */
2101 #ifdef SCIP_OUTPUT
2102  SCIP_CALL( SCIPsetSubscipsOff(subscip, FALSE) );
2103 #else
2104  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); /* quiet */
2105 #endif
2106  }
2107  else
2108  {
2109  /* avoid recursive call */
2110  if ( ! SCIPisParamFixed(subscip, "separating/cgmip/freq") )
2111  {
2112  SCIP_CALL( SCIPsetIntParam(subscip, "separating/cgmip/freq", -1) );
2113  }
2114  }
2115 
2116 #ifdef SCIP_DISABLED_CODE
2117  /* the following possibly helps to improve performance (untested) */
2118  SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) );
2119 #else
2120 
2121  /* zirounding is often successful, so allow it some more calls */
2122  if ( ! SCIPisParamFixed(subscip, "heuristics/zirounding/minstopncalls") )
2123  {
2124  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/zirounding/minstopncalls", 10000) );
2125  }
2126 
2127  if ( sepadata->subscipfast )
2128  {
2129  /* set other heuristics */
2130  if ( ! SCIPisParamFixed(subscip, "heuristics/shifting/freq") )
2131  {
2132  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/shifting/freq", 3) );
2133  }
2134  if ( ! SCIPisParamFixed(subscip, "heuristics/simplerounding/freq") )
2135  {
2136  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/simplerounding/freq", 1) );
2137  }
2138  if ( ! SCIPisParamFixed(subscip, "heuristics/rounding/freq") )
2139  {
2140  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/rounding/freq", 1) );
2141  }
2142  if ( ! SCIPisParamFixed(subscip, "heuristics/oneopt/freq") )
2143  {
2144  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/oneopt/freq", 1) );
2145  }
2146 
2147  /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/pscostdiving/freq", 1) ); */
2148  /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", 3) ); */
2149 
2150  /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/coefdiving/freq", -1) ); */
2151  /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) ); */
2152  /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/guideddiving/freq", -1) ); */
2153  /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/linesearchdiving/freq", -1) ); */
2154  /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/objpscostdiving/freq", -1) ); */
2155  /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/rootsoldiving/freq", -1) ); */
2156  /* SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/veclendiving/freq", -1) ); */
2157 
2158  /* use fast presolving */
2159  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
2160 
2161  /* disable conflict analysis */
2162  /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useprop", FALSE) ); */
2163  /* SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useinflp", 'o') ); */
2164  /* SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); */
2165  /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usesb", FALSE) ); */
2166  /* SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usepseudo", FALSE) ); */
2167 
2168  /* use fast separation */
2169  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
2170  }
2171 #endif
2172 
2173 #ifdef SCIP_WRITEPROB
2174  {
2175  char name[SCIP_MAXSTRLEN];
2176 
2177  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgsepa%s%s%s%s_%s.set",
2178  sepadata->objlone ? "_l1" : "",
2179  sepadata->addviolationcons ? "_vc" : "",
2180  sepadata->skipmultbounds ? "_ub" : "",
2181  sepadata->primalseparation ? "_ps" : "",
2182  SCIPgetProbName(mipdata->scip));
2183  SCIP_CALL( SCIPwriteParams(subscip, name, TRUE, FALSE) );
2184  SCIPinfoMessage(mipdata->scip, NULL, "Wrote settings to file <%s>.\n", name);
2185  }
2186 #endif
2187 
2188  return SCIP_OKAY;
2189 }
2190 
2191 
2192 /** try to convert fractional gomory cuts to primal solutions of CG-MIP */
2193 static
2194 SCIP_RETCODE createCGMIPprimalsols(
2195  SCIP* scip, /**< original SCIP data structure */
2196  SCIP_SEPADATA* sepadata, /**< separator data */
2197  CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
2198  )
2199 {
2200  SCIP_VAR** vars;
2201  SCIP_ROW** rows;
2202  SCIP_COL** cols;
2203  SCIP_Real* binvrow;
2204  SCIP_Real* cutcoefs;
2205  int* basisind;
2206  int nvars;
2207  int nrows;
2208  int ncols;
2209  int ngen = 0;
2210  int ntried = 0;
2211  int i;
2212 
2213  assert( scip != NULL );
2214  assert( sepadata != NULL );
2215  assert( mipdata != NULL );
2216 
2217  /* get variables */
2218  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2219 
2220  /* get rows and columns */
2221  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
2222  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
2223  assert( ncols <= nvars );
2224 
2225  /* get storage */
2226  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
2227  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
2228  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
2229 
2230  /* get basis indices */
2231  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
2232 
2233  /* loop through rows */
2234  for (i = 0; i < nrows; ++i)
2235  {
2236  SCIP_Bool tryrow = FALSE;
2237  SCIP_Real primsol = SCIP_INVALID;
2238  int c;
2239  int r;
2240 
2241  c = basisind[i];
2242  assert( c < ncols );
2243 
2244  if ( c >= 0 )
2245  {
2246  SCIP_VAR* var;
2247 
2248  var = SCIPcolGetVar(cols[c]);
2249 
2250  if ( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
2251  {
2252  primsol = SCIPcolGetPrimsol(cols[c]);
2253  assert( SCIPgetVarSol(scip, var) == primsol ); /*lint !e777*/
2254 
2255  if ( SCIPfeasFrac(scip, primsol) >= AWAY && SCIPfeasFrac(scip, primsol) <= 1 - AWAY )
2256  tryrow = TRUE;
2257  }
2258  }
2259 #if ( SEPARATEROWS == TRUE )
2260  else
2261  {
2262  SCIP_ROW* row;
2263 
2264  assert(0 <= -c-1 && -c-1 < nrows);
2265 
2266  row = rows[-c-1];
2267 
2268  if ( SCIProwIsIntegral(row) && ! SCIProwIsModifiable(row) )
2269  {
2270  /* Compute value of the slack variable (we only care about the correct fractionality) */
2271  if ( SCIPisInfinity(scip, SCIProwGetRhs(row)) )
2272  primsol = SCIProwGetLhs(row) - SCIPgetRowLPActivity(scip, row);
2273  else
2274  primsol = SCIProwGetRhs(row) - SCIPgetRowLPActivity(scip, row);
2275 
2276  if ( SCIPfeasFrac(scip, primsol) >= AWAY && SCIPfeasFrac(scip, primsol) <= 1 - AWAY )
2277  tryrow = TRUE;
2278  }
2279  }
2280 #endif
2281 
2282  if ( tryrow )
2283  {
2284  SCIP_Bool success;
2285  SCIP_SOL* sol;
2286  SCIP_Real cutrhs = 0.0;
2287  SCIP_ROW* row;
2288  SCIP_Real val;
2289  int j;
2290 
2291  assert( primsol != SCIP_INVALID ); /*lint !e777*/
2292 
2293  /* get the row of B^-1 for this basic integer variable with fractional solution value */
2294  SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow, NULL, NULL) );
2295 
2296  /* clear cutcoefs */
2297  BMSclearMemoryArray(cutcoefs, ncols);
2298 
2299  /* create solution */
2300  SCIP_CALL( SCIPcreateSol(mipdata->subscip, &sol, NULL) );
2301 
2302  /* add values of multipliers to solution and compute coefficients */
2303  for (r = 0; r < nrows; ++r)
2304  {
2305  SCIP_COL** rowcols;
2306  SCIP_Real* rowvals;
2307  SCIP_Real binvval;
2308  SCIP_Real weight;
2309 
2310  row = rows[r];
2311  assert( row != NULL );
2312 
2313  binvval = binvrow[r];
2314  binvval = SCIPfrac(scip, binvval); /* can always take fractional value */
2315  if ( ! SCIPisFeasZero(scip, binvval) )
2316  {
2317  SCIP_Real lhs;
2318  SCIP_Real rhs;
2319  SCIP_Bool uselhs;
2320 
2321  lhs = SCIProwGetLhs(row);
2322  rhs = SCIProwGetRhs(row);
2323 
2324  if ( ! SCIPisEQ(scip, lhs, rhs) )
2325  {
2326  SCIP_BASESTAT stat;
2327 
2328  stat = SCIProwGetBasisStatus(row);
2329 
2330  if ( stat == SCIP_BASESTAT_LOWER )
2331  {
2332  assert( ! SCIPisInfinity(scip, -lhs) );
2333  uselhs = TRUE;
2334  }
2335  else if ( stat == SCIP_BASESTAT_UPPER )
2336  {
2337  assert( ! SCIPisInfinity(scip, rhs) );
2338  uselhs = FALSE;
2339  }
2340  else if ( SCIPisInfinity(scip, rhs) )
2341  uselhs = TRUE;
2342  else
2343  uselhs = FALSE;
2344  }
2345  else if ( binvval < 0.0 )
2346  uselhs = TRUE;
2347  else
2348  uselhs = FALSE;
2349 
2350  if ( uselhs )
2351  {
2352  assert( mipdata->ylhs[r] != NULL );
2353  SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->ylhs[r], fabs(binvval)) );
2354  weight = -fabs(binvval);
2355  }
2356  else
2357  {
2358  assert( mipdata->yrhs[r] != NULL );
2359  SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->yrhs[r], fabs(binvval)) );
2360  weight = fabs(binvval);
2361  }
2362 
2363  /* update cut coefficients */
2364  rowcols = SCIProwGetCols(row);
2365  rowvals = SCIProwGetVals(row);
2366 
2367  /* add the row coefficients to the sum */
2368  for (j = 0; j < SCIProwGetNLPNonz(row); ++j)
2369  {
2370  int idx;
2371 
2372  assert( rowcols[j] != NULL );
2373 
2374  idx = SCIPcolGetLPPos(rowcols[j]);
2375  assert( 0 <= idx && idx < ncols );
2376 
2377  cutcoefs[idx] += weight * rowvals[j];
2378  }
2379 
2380  /* compute rhs */
2381  if ( uselhs )
2382  {
2383  assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
2384  val = mipdata->lhs[r];
2385  }
2386  else
2387  {
2388  assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) );
2389  val = mipdata->rhs[r];
2390  }
2391  cutrhs += weight * val;
2392  }
2393  }
2394 
2395  /* fill in values of cut */
2396  for (c = 0; c < ncols; ++c)
2397  {
2398  if ( mipdata->coltype[c] != colPresent )
2399  continue;
2400 
2401  val = SCIPfloor(scip, cutcoefs[c]);
2402  if ( mipdata->iscomplemented[c] )
2403  val = -val;
2404  if ( ! SCIPisFeasZero(scip, val) )
2405  {
2406  SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->alpha[c], val) );
2407  }
2408  val = SCIPfeasFrac(scip, cutcoefs[c]);
2409  if ( ! SCIPisFeasZero(scip, val) )
2410  {
2411  SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->fracalpha[c], val) );
2412  }
2413  }
2414 
2415  if ( ! SCIPisFeasZero(scip, SCIPfloor(scip, cutrhs)) )
2416  {
2417  SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->beta, SCIPfloor(scip, cutrhs)) );
2418  }
2419  if ( ! SCIPisFeasZero(scip, SCIPfeasFrac(scip, cutrhs)) )
2420  {
2421  SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->fracbeta, SCIPfeasFrac(scip, cutrhs)) );
2422  }
2423 
2424  SCIP_CALL( SCIPtrySolFree(mipdata->subscip, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
2425  ++ntried;
2426  if ( success )
2427  ++ngen;
2428  }
2429  }
2430 
2431  SCIPfreeBufferArray(scip, &cutcoefs);
2432  SCIPfreeBufferArray(scip, &binvrow);
2433  SCIPfreeBufferArray(scip, &basisind);
2434 
2435  SCIPdebugMsg(scip, "Created %d primal solutions for CG-MIP from tableau cuts (tried: %d).\n", ngen, ntried);
2436 
2437  return SCIP_OKAY;
2438 }
2439 
2440 
2441 /** solve subscip */
2442 static
2443 SCIP_RETCODE solveSubscip(
2444  SCIP* origscip, /**< SCIP data structure */
2445  SCIP_SEPADATA* sepadata, /**< separator data */
2446  CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
2447  SCIP_Bool* success /**< if setting was successful -> stop */
2448  )
2449 {
2450  SCIP* subscip;
2451  SCIP_RETCODE retcode;
2452  SCIP_STATUS status;
2453  SCIP_Real timelimit;
2454  SCIP_Real memorylimit;
2455  SCIP_Longint nodelimit;
2456 
2457  assert( origscip != NULL );
2458  assert( sepadata != NULL );
2459  assert( mipdata != NULL );
2460  assert( success != NULL );
2461 
2462  *success = TRUE;
2463 
2464  subscip = mipdata->subscip;
2465 
2466  SCIP_CALL( SCIPcheckCopyLimits(origscip, success) );
2467 
2468  if ( ! (*success) )
2469  return SCIP_OKAY;
2470 
2471  /* @todo Check whether copying the parameters is useful */
2472  /* SCIP_CALL( SCIPcopyLimits(origscip, subscip) ); */
2473 
2474  /* determine time limit */
2475  SCIP_CALL( SCIPgetRealParam(origscip, "limits/time", &timelimit) );
2476  if ( sepadata->timelimit < timelimit )
2477  timelimit = sepadata->timelimit;
2478 
2479  if ( ! SCIPisInfinity(origscip, timelimit) )
2480  {
2481  timelimit -= SCIPgetSolvingTime(origscip);
2482  if ( timelimit > 0.0 )
2483  {
2484  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
2485  }
2486  else
2487  {
2488  SCIPdebugMsg(origscip, "Reached timelimit.\n");
2489  *success = FALSE;
2490  return SCIP_OKAY;
2491  }
2492  }
2493 
2494  /* determine memory limit */
2495  SCIP_CALL( SCIPgetRealParam(origscip, "limits/memory", &memorylimit) );
2496  if ( sepadata->memorylimit < memorylimit )
2497  memorylimit = sepadata->memorylimit;
2498 
2499  if ( ! SCIPisInfinity(origscip, memorylimit) )
2500  {
2501  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
2502  memorylimit -= SCIPgetMemUsed(origscip)/1048576.0;
2503  memorylimit -= SCIPgetMemExternEstim(origscip)/1048576.0;
2504  if ( memorylimit > 0.0 )
2505  {
2506  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
2507  }
2508  else
2509  {
2510  SCIPdebugMsg(origscip, "Reached memorylimit.\n");
2511  *success = TRUE;
2512  return SCIP_OKAY;
2513  }
2514  }
2515 
2516  /* set node limit for subproblem */
2517  if ( sepadata->minnodelimit < 0 || sepadata->maxnodelimit < 0 )
2518  nodelimit = SCIP_LONGINT_MAX;
2519  else
2520  {
2521  assert( sepadata->minnodelimit >= 0 && sepadata->maxnodelimit >= 0 );
2522  nodelimit = SCIPgetNLPIterations(origscip);
2523  nodelimit = MAX(sepadata->minnodelimit, nodelimit);
2524  nodelimit = MIN(sepadata->maxnodelimit, nodelimit);
2525  }
2526  assert( nodelimit >= 0 );
2527  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
2528 
2529  /* try to create primal solutions of CG-MIP problem via tableau cuts */
2530  if ( sepadata->genprimalsols )
2531  {
2532  SCIP_CALL( SCIPtransformProb(subscip) );
2533  SCIP_CALL( createCGMIPprimalsols(origscip, sepadata, mipdata) );
2534  }
2535 
2536  SCIPdebugMsg(origscip, "Solving sub-SCIP (time limit: %f mem limit: %f node limit: %" SCIP_LONGINT_FORMAT ") ...\n", timelimit, memorylimit, nodelimit);
2537 
2538  /* disable statistic timing inside sub SCIP */
2539  if ( ! sepadata->output )
2540  {
2541  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
2542  }
2543 
2544  /* check whether we want a complete solve */
2545  if ( ! sepadata->earlyterm )
2546  {
2547  retcode = SCIPsolve(subscip);
2548  SCIPdebugMsg(origscip, "Finished solving CG-MIP (dualbound: %g, solving time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ", nodelimit: %" SCIP_LONGINT_FORMAT").\n",
2549  SCIPgetDualbound(subscip), SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), nodelimit);
2550 
2551  /* errors in solving the subproblem should not kill the overall solving process;
2552  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
2553  if ( retcode != SCIP_OKAY )
2554  {
2555 #ifndef NDEBUG
2556  SCIP_CALL( retcode );
2557 #endif
2558  SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2559  *success = FALSE;
2560  return SCIP_OKAY;
2561  }
2562 
2563  status = SCIPgetStatus(subscip);
2564 
2565 #ifdef SCIP_OUTPUT
2566  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2567 #else
2568  if ( sepadata->output )
2569  {
2570  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2571  }
2572 #endif
2573 
2574  /* if the problem is infeasible (can happen because of violation constraint) */
2575  if ( status == SCIP_STATUS_INFEASIBLE || status == SCIP_STATUS_INFORUNBD )
2576  {
2577  SCIPdebugMsg(origscip, "CG-MIP separation problem infeasible.\n");
2578  *success = FALSE;
2579  return SCIP_OKAY;
2580  }
2581 
2582  /* if the solution ran into the time limit */
2583  if ( status == SCIP_STATUS_TIMELIMIT )
2584  {
2585  SCIPdebugMsg(origscip, "CG-MIP separation problem ran into time limit.\n");
2586  *success = FALSE;
2587  return SCIP_OKAY;
2588  }
2589 
2590  /* if the solution process was terminated */
2591  if ( status == SCIP_STATUS_USERINTERRUPT )
2592  {
2593  SCIPdebugMsg(origscip, "CG-MIP separation problem stopped by user interrupt.\n");
2594  *success = FALSE;
2595  return SCIP_OKAY;
2596  }
2597 
2598  /* all other statuses except optimal or node limit are invalid */
2599  if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_NODELIMIT )
2600  {
2601  SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2602  return SCIP_ERROR;
2603  }
2604  }
2605  else
2606  {
2607  /* otherwise we want a heuristic solve */
2608 
2609  /* -> solve until first solution is found */
2610  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", 1) );
2611  retcode = SCIPsolve(subscip);
2612  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", -1) );
2613 
2614  /* errors in solving the subproblem should not kill the overall solving process;
2615  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
2616  if ( retcode != SCIP_OKAY )
2617  {
2618 #ifndef NDEBUG
2619  SCIP_CALL( retcode );
2620 #endif
2621  SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2622  *success = FALSE;
2623  return SCIP_OKAY;
2624  }
2625 
2626  status = SCIPgetStatus(subscip);
2627 
2628  /* if the solution process was terminated or the problem is infeasible (can happen because of violation constraint) */
2629  if ( status == SCIP_STATUS_TIMELIMIT || status == SCIP_STATUS_USERINTERRUPT || status == SCIP_STATUS_NODELIMIT ||
2630  status == SCIP_STATUS_INFEASIBLE || status == SCIP_STATUS_INFORUNBD || status == SCIP_STATUS_MEMLIMIT )
2631  {
2632  /* output statistics before stopping */
2633 #ifdef SCIP_OUTPUT
2634  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2635 #else
2636  if ( sepadata->output )
2637  {
2638  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2639  }
2640 #endif
2641  *success = FALSE;
2642  return SCIP_OKAY;
2643  }
2644 
2645  /* all other statuses except optimal or bestsollimit are invalid - (problem cannot be infeasible) */
2646  if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_BESTSOLLIMIT )
2647  {
2648  SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2649  return SCIP_ERROR;
2650  }
2651 
2652  /* solve some more, if a feasible solution was found */
2653  if ( status == SCIP_STATUS_BESTSOLLIMIT )
2654  {
2655  SCIPdebugMsg(origscip, "Continue solving separation problem (current time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ") ...\n",
2656  SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip));
2657 
2658  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", STALLNODELIMIT) );
2659  retcode = SCIPsolve(subscip);
2660  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", -1LL) );
2661 
2662  SCIPdebugMsg(origscip, "Finished solving CG-MIP (dualbound: %g, solving time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ", nodelimit: %" SCIP_LONGINT_FORMAT").\n",
2663  SCIPgetDualbound(subscip), SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), nodelimit);
2664 
2665  /* errors in solving the subproblem should not kill the overall solving process;
2666  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
2667  if ( retcode != SCIP_OKAY )
2668  {
2669 #ifndef NDEBUG
2670  SCIP_CALL( retcode );
2671 #endif
2672  SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2673  *success = FALSE;
2674  return SCIP_OKAY;
2675  }
2676 
2677  status = SCIPgetStatus(subscip);
2678  assert( status != SCIP_STATUS_BESTSOLLIMIT );
2679 
2680 #ifdef SCIP_OUTPUT
2681  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2682 #else
2683  if ( sepadata->output )
2684  {
2685  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2686  }
2687 #endif
2688 
2689  /* if the solution process was terminated */
2690  if ( status == SCIP_STATUS_TIMELIMIT || status == SCIP_STATUS_USERINTERRUPT || status == SCIP_STATUS_MEMLIMIT )
2691  {
2692  *success = FALSE;
2693  return SCIP_OKAY;
2694  }
2695 
2696  /* all other statuses except optimal or bestsollimit are invalid */
2697  if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_STALLNODELIMIT && status != SCIP_STATUS_NODELIMIT )
2698  {
2699  SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2700  return SCIP_ERROR;
2701  }
2702  }
2703  }
2704 
2705  return SCIP_OKAY;
2706 }
2707 
2708 /** Computes cut from the given multipliers
2709  *
2710  * When computing the cut, we take the fractional part of the multipliers. This is known to produce stronger cuts in
2711  * the pure integer case, since the cut is the sum of the one using fractional parts and integer multiples of the
2712  * original constraints. However, if there are continuous variables, the resulting cut might not be valid. This is
2713  * checked and returned.
2714  *
2715  * Moreover, the cut computed here in general will not be the same as the one computed with the
2716  * sub-MIP, because of numerical differences. Here, we only combine rows whose corresponding
2717  * multiplier is positive w.r.t. the feasibility tolerance. In the sub-MIP, however, the rows are
2718  * combined in any case. This makes a difference, if the coefficients in the matrix are large and
2719  * hence yield a value that is larger than the tolerance.
2720  *
2721  * Because of the transformations we have the following:
2722  *
2723  * If variable \f$x_j\f$ was complemented, we have \f$x'_j = u_j - x_j\f$. If in the transformed
2724  * system the lower bound is used, its corresponding multiplier is \f$y^T A'_j - \lfloor y^T A'_j
2725  * \rfloor\f$, which corresponds to
2726  * \f[
2727  * 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
2728  * \f]
2729  * in the original system.
2730  *
2731  * If such a variable was at its upper bound before the transformation, it is at its lower bound
2732  * afterwards. Hence, its contribution to the cut is 0.
2733  *
2734  * Note that if the original LP-solution does not satisfy some of the rows with equality, the
2735  * violation of the cut might be smaller than what is computed with the reduced sub-MIP.
2736  *
2737  * Furthermore, note that if continuous variables have been shifted, the computed violation may be
2738  * different as well, because the necessary changes in the lhs/rhs are not used here anymore.
2739  *
2740  * @todo Check if cut is correct if continuous variables have been shifted.
2741  */
2742 static
2743 SCIP_RETCODE computeCut(
2744  SCIP* scip, /**< original scip */
2745  SCIP_SEPA* sepa, /**< separator */
2746  CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
2747  SCIP_SEPADATA* sepadata, /**< separator data */
2748  SCIP_SOL* sol, /**< current solution for sub-MIP */
2749  SCIP_Bool usefrac, /**< use fractional value of multipliers */
2750  SCIP_Real* cutcoefs, /**< coefficients of the cut */
2751  SCIP_Real* cutrhs, /**< rhs of the cut */
2752  SCIP_Bool* localrowsused, /**< pointer to store whether local rows were used in summation */
2753  SCIP_Bool* localboundsused, /**< pointer to store whether local bounds were used in summation */
2754  int* cutrank, /**< pointer to store the cut rank */
2755  SCIP_Bool* success /**< whether we produced a valid cut */
2756  )
2757 {
2758  SCIP* subscip;
2759  SCIP_VAR** vars;
2760  SCIP_ROW** rows;
2761  SCIP_COL** cols;
2762  SCIP_Real val;
2763  SCIP_Real maxabsweight;
2764  int nvars;
2765  int ncols;
2766  int nrows;
2767  int i;
2768  int j;
2769 
2770  assert( scip != NULL );
2771  assert( mipdata != NULL );
2772  assert( sepadata != NULL );
2773  assert( cutcoefs != NULL );
2774  assert( cutrhs != NULL );
2775  assert( localrowsused != NULL );
2776  assert( localboundsused != NULL );
2777  assert( cutrank != NULL );
2778  assert( success != NULL );
2779 
2780  /* initialize */
2781  *localrowsused = FALSE;
2782  *localboundsused = FALSE;
2783  *cutrank = 0;
2784  *success = TRUE;
2785 
2786  subscip = mipdata->subscip;
2787  assert( subscip != NULL );
2788 
2789  /* get data */
2790  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2791  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
2792  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
2793  assert( nrows == (int) mipdata->nrows );
2794  assert( ncols == (int) mipdata->ncols );
2795 
2796  BMSclearMemoryArray(cutcoefs, nvars);
2797  *cutrhs = 0.0;
2798 
2799  /* find maximal absolute weight */
2800  maxabsweight = 0.0;
2801  for (i = 0; i < nrows; ++i)
2802  {
2803  SCIP_ROW* row;
2804  SCIP_Real absweight = 0.0;
2805 
2806  row = rows[i];
2807  assert( row != NULL );
2808 
2809  /* skip modifiable rows and local rows, unless allowed */
2810  if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
2811  {
2812  assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL );
2813  continue;
2814  }
2815 
2816  /* get weight from solution (take larger of the values of lhs/rhs) */
2817  if ( mipdata->ylhs[i] != NULL )
2818  {
2819  val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[i]);
2820 
2821  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2822  if ( usefrac )
2823  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2824 
2825  if ( SCIPisFeasPositive(scip, val) )
2826  absweight = val;
2827 
2828  assert( ! sepadata->onlyrankone || SCIProwGetOriginSepa(row) != sepa );
2829  }
2830  if ( mipdata->yrhs[i] != NULL )
2831  {
2832  val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[i]);
2833 
2834  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2835  if ( usefrac )
2836  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2837 
2838  /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
2839  if ( SCIPisFeasGT(scip, val, absweight) )
2840  absweight = val;
2841 
2842  assert( ! sepadata->onlyrankone || SCIProwGetOriginSepa(row) != sepa );
2843  }
2844  assert( ! SCIPisNegative(scip, absweight) );
2845 
2846  if ( absweight > maxabsweight )
2847  maxabsweight = absweight;
2848  }
2849 
2850  /* get weight from objective cuts */
2851  if ( sepadata->useobjub || sepadata->useobjlb )
2852  {
2853  SCIP_Real absweight = 0.0;
2854 
2855  assert( mipdata->ntotalrows == mipdata->nrows + 1 );
2856 
2857  if ( mipdata->ylhs[mipdata->nrows] != NULL )
2858  {
2859  val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]);
2860  if ( usefrac )
2861  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2862 
2863  if ( SCIPisFeasPositive(scip, val) )
2864  absweight = val;
2865  }
2866  if ( mipdata->yrhs[mipdata->nrows] != NULL )
2867  {
2868  val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]);
2869  if ( usefrac )
2870  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2871 
2872  /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
2873  if ( SCIPisFeasGT(scip, val, absweight) )
2874  absweight = val;
2875  }
2876 
2877  if ( absweight > maxabsweight )
2878  maxabsweight = absweight;
2879  }
2880 
2881  /* calculate the row summation */
2882  for (i = 0; i < nrows; ++i)
2883  {
2884  SCIP_ROW* row;
2885  SCIP_Real weight;
2886  SCIP_Real absweight;
2887  SCIP_Bool uselhs;
2888 
2889  row = rows[i];
2890  assert( row != NULL );
2891 
2892  /* skip modifiable rows and local rows, unless allowed */
2893  if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && ! sepadata->allowlocal) )
2894  {
2895  assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL );
2896  continue;
2897  }
2898 
2899  /* get weight from solution */
2900  weight = 0.0;
2901  uselhs = FALSE;
2902  if ( mipdata->ylhs[i] != NULL )
2903  {
2904  val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[i]);
2905  assert( ! SCIPisFeasNegative(subscip, val) );
2906 
2907  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2908  if ( usefrac )
2909  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2910 
2911  if ( SCIPisFeasPositive(scip, val) )
2912  {
2913  uselhs = TRUE;
2914  weight = -val;
2915  }
2916  }
2917  if ( mipdata->yrhs[i] != NULL )
2918  {
2919  val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[i]);
2920  assert( ! SCIPisFeasNegative(subscip, val) );
2921 
2922  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2923  if ( usefrac )
2924  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
2925 
2926  /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
2927  if ( SCIPisFeasGT(scip, val, REALABS(weight)) )
2928  {
2929  uselhs = FALSE;
2930  weight = val;
2931  }
2932  }
2933 
2934  /* add row if weight is nonzero and lies within range */
2935  absweight = REALABS(weight);
2936  if ( ! SCIPisSumZero(scip, weight) && absweight * MAXWEIGHTRANGE >= maxabsweight )
2937  {
2938  SCIP_COL** rowcols;
2939  SCIP_Real* rowvals;
2940 
2941  rowcols = SCIProwGetCols(row);
2942  rowvals = SCIProwGetVals(row);
2943 
2944  /* add the row coefficients to the sum */
2945  for (j = 0; j < SCIProwGetNLPNonz(row); ++j)
2946  {
2947  SCIP_VAR* var;
2948  int idx;
2949 
2950  assert( rowcols[j] != NULL );
2951  var = SCIPcolGetVar(rowcols[j]);
2952 
2953  assert( var != NULL );
2954  assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
2955  assert( SCIPvarGetCol(var) == rowcols[j] );
2956 
2957  idx = SCIPvarGetProbindex(var);
2958  assert( 0 <= idx && idx < nvars );
2959 
2960  cutcoefs[idx] += weight * rowvals[j];
2961  }
2962 
2963  /* compute rhs */
2964  if ( uselhs )
2965  {
2966  assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
2967  val = SCIProwGetLhs(row) - SCIProwGetConstant(row);
2968  if ( SCIProwIsIntegral(row) )
2969  val = SCIPfeasCeil(scip, val); /* row is integral: round left hand side up */
2970  }
2971  else
2972  {
2973  assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) );
2974  val = SCIProwGetRhs(row) - SCIProwGetConstant(row);
2975  if ( SCIProwIsIntegral(row) )
2976  val = SCIPfeasFloor(scip, val); /* row is integral: round right hand side down */
2977  }
2978  *cutrhs += weight * val;
2979 
2980  *localrowsused = *localrowsused || SCIProwIsLocal(row);
2981 
2982  if ( SCIProwGetRank(row) > *cutrank )
2983  *cutrank = SCIProwGetRank(row);
2984  }
2985  }
2986  /* add 1 to cutrank */
2987  ++(*cutrank);
2988 
2989  /* get weight from objective bounds */
2990  if ( sepadata->useobjub || sepadata->useobjlb )
2991  {
2992  SCIP_Real weight = 0.0;
2993  SCIP_Bool uselhs = FALSE;
2994  SCIP_Real absweight;
2995 
2996  assert( mipdata->ntotalrows == mipdata->nrows + 1 );
2997 
2998  if ( mipdata->ylhs[mipdata->nrows] != NULL )
2999  {
3000  val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]);
3001  assert( ! SCIPisFeasNegative(subscip, val) );
3002  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3003  if ( usefrac )
3004  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3005 
3006  if ( SCIPisFeasPositive(scip, val) )
3007  {
3008  uselhs = TRUE;
3009  weight = -val;
3010  }
3011  }
3012  if ( mipdata->yrhs[mipdata->nrows] != NULL )
3013  {
3014  val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]);
3015  assert( ! SCIPisFeasNegative(subscip, val) );
3016  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3017  if ( usefrac )
3018  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3019 
3020  /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
3021  if ( SCIPisFeasGT(scip, val, REALABS(weight)) )
3022  {
3023  uselhs = FALSE;
3024  weight = val;
3025  }
3026  }
3027 
3028  /* add objective row if weight is nonzero and lies within range */
3029  absweight = REALABS(weight);
3030  if ( ! SCIPisSumZero(scip, weight) && absweight * MAXWEIGHTRANGE >= maxabsweight )
3031  {
3032  SCIP_Real obj = 0.0;
3033  int idx;
3034 
3035  /* add the objective row coefficients to the sum */
3036  for (j = 0; j < ncols; ++j)
3037  {
3038  assert( cols[j] != NULL );
3039 
3040  obj = SCIPcolGetObj(cols[j]);
3041  if ( ! SCIPisZero(scip, obj) )
3042  {
3043  idx = SCIPvarGetProbindex( SCIPcolGetVar(cols[j]) );
3044  assert( 0 <= idx && idx < nvars );
3045  cutcoefs[idx] += weight * obj;
3046  }
3047  }
3048 
3049  /* compute rhs */
3050  if ( uselhs )
3051  {
3052  val = SCIPgetLowerbound(scip);
3053  assert( ! SCIPisInfinity(scip, -val) );
3054  if ( SCIPisObjIntegral(scip) )
3055  val = SCIPfeasCeil(scip, val); /* objective is integral: round left hand side up */
3056  }
3057  else
3058  {
3059  val = SCIPgetUpperbound(scip);
3060  assert( ! SCIPisInfinity(scip, val) );
3061  if ( SCIPisObjIntegral(scip) )
3062  val = SCIPfeasFloor(scip, val); /* objective is integral: round right hand side down */
3063  }
3064  *cutrhs += weight * val;
3065  }
3066  }
3067 
3068  /* add upper bounds */
3069  for (j = 0; j < ncols; ++j)
3070  {
3071  assert( cols[j] != NULL );
3072  if ( mipdata->z[j] != NULL )
3073  {
3074  assert( mipdata->coltype[j] == colPresent );
3075 
3076  val = SCIPgetSolVal(subscip, sol, mipdata->z[j]);
3077  assert( ! SCIPisFeasNegative(subscip, val) );
3078 
3079  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3080  if ( usefrac )
3081  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3082 
3083  /* if a bound has been used */
3084  if ( SCIPisSumPositive(subscip, val) )
3085  {
3086  SCIP_VAR* var;
3087  int idx;
3088 
3089  var = SCIPcolGetVar(cols[j]);
3090 
3091  assert( var != NULL );
3092  assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
3093  assert( SCIPvarIsIntegral(var) );
3094  assert( SCIPvarGetCol(var) == cols[j] );
3095 
3096  idx = SCIPvarGetProbindex(var);
3097  assert( 0 <= idx && idx < nvars );
3098 
3099  /* check whether variable is complemented */
3100  if ( mipdata->iscomplemented[j] )
3101  {
3102  SCIP_Real lbnd;
3103  lbnd = SCIPvarGetLbGlobal(var);
3104  assert( ! SCIPisInfinity(scip, -lbnd) );
3105  assert( SCIPisIntegral(scip, lbnd) );
3106  assert( SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPcolGetLb(cols[j])) );
3107 
3108  /* variable should not be free */
3109  assert( ! SCIPisInfinity(scip, -lbnd) || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) );
3110 
3111  /* if allowed, try to use stronger local bound */
3112  if ( sepadata->allowlocal && SCIPvarGetLbLocal(var) - 0.5 > lbnd )
3113  {
3114  lbnd = SCIPvarGetLbLocal(var);
3115  assert( SCIPisIntegral(scip, lbnd) );
3116  *localboundsused = TRUE;
3117  }
3118 
3119  cutcoefs[idx] -= val;
3120  *cutrhs -= lbnd * val;
3121  }
3122  else
3123  {
3124  SCIP_Real ubnd;
3125  ubnd = SCIPvarGetUbGlobal(var);
3126  assert( ! SCIPisInfinity(scip, ubnd) );
3127  assert( SCIPisIntegral(scip, ubnd) );
3128  assert( SCIPisEQ(scip, SCIPvarGetUbLocal(var), SCIPcolGetUb(cols[j])) );
3129 
3130  /* if allowed, try to use stronger local bound */
3131  if ( sepadata->allowlocal && SCIPvarGetUbLocal(var) + 0.5 < ubnd )
3132  {
3133  ubnd = SCIPvarGetUbLocal(var);
3134  assert( SCIPisIntegral(scip, ubnd) );
3135  *localboundsused = TRUE;
3136  }
3137 
3138  cutcoefs[idx] += val;
3139  *cutrhs += ubnd * val;
3140  }
3141  }
3142  }
3143  }
3144 
3145  /* check lower bounds for integral variables */
3146  for (j = 0; j < nvars; ++j)
3147  {
3148  SCIP_VAR* var;
3149  int pos;
3150 
3151  var = vars[j];
3152  assert( var != NULL );
3153  pos = SCIPcolGetLPPos(SCIPvarGetCol(var));
3154 
3155  /* a variable may have status COLUMN, but the corresponding column may not (yet) be in the LP */
3156  if ( pos >= 0 && mipdata->coltype[pos] != colContinuous && mipdata->coltype[pos] != colConverted )
3157  {
3158  assert( pos < ncols );
3159  assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
3160  assert( SCIPvarIsIntegral(var) );
3161 
3162  /* check whether variable is complemented */
3163  if ( mipdata->iscomplemented[pos] )
3164  {
3165  assert( ! mipdata->isshifted[pos] );
3166  /* if the variable is complemented, the multiplier for the upper bound arises from the
3167  lower bound multiplier for the transformed problem - because of the minus-sign in the
3168  transformation this yields a round-up operation. */
3169  val = SCIPfeasCeil(scip, cutcoefs[j]) - cutcoefs[j];
3170  assert( ! SCIPisFeasNegative(scip, val) );
3171 
3172  /* only if variable needs to be rounded */
3173  if ( SCIPisSumPositive(scip, val) )
3174  {
3175  SCIP_Real ubnd;
3176  ubnd = SCIPvarGetUbGlobal(var);
3177  assert( ! SCIPisInfinity(scip, ubnd) );
3178  assert( SCIPisIntegral(scip, ubnd) );
3179 
3180  /* variable should not be free */
3181  assert( ! SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) || ! SCIPisInfinity(scip, ubnd) );
3182 
3183  /* if allowed, try to use stronger local bound */
3184  if ( sepadata->allowlocal && SCIPvarGetUbLocal(var) + 0.5 < ubnd )
3185  {
3186  ubnd = SCIPvarGetUbLocal(var);
3187  assert( SCIPisIntegral(scip, ubnd) );
3188  *localboundsused = TRUE;
3189  }
3190 
3191  /* round cut coefficients, i.e., add val to cutcoefs[j] */
3192  cutcoefs[j] = SCIPfeasCeil(scip, cutcoefs[j]);
3193 
3194  /* correct rhs */
3195  if ( ! SCIPisSumZero(scip, ubnd) )
3196  *cutrhs += ubnd * val;
3197  }
3198  }
3199  else
3200  {
3201  /* compute multiplier for lower bound: */
3202  val = cutcoefs[j] - SCIPfeasFloor(scip, cutcoefs[j]);
3203  assert( ! SCIPisFeasNegative(scip, val) );
3204 
3205  /* only if variable needs to be rounded */
3206  if ( SCIPisSumPositive(scip, val) )
3207  {
3208  SCIP_Real lbnd;
3209  lbnd = SCIPvarGetLbGlobal(var);
3210  assert( ! SCIPisInfinity(scip, -lbnd) );
3211  assert( SCIPisIntegral(scip, lbnd) );
3212 
3213  /* variable should not be free */
3214  assert( ! SCIPisInfinity(scip, -lbnd) || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) );
3215 
3216  /* if allowed, try to use stronger local bound */
3217  if ( sepadata->allowlocal && SCIPvarGetLbLocal(var) - 0.5 > lbnd )
3218  {
3219  lbnd = SCIPvarGetLbLocal(var);
3220  assert( SCIPisIntegral(scip, lbnd) );
3221  *localboundsused = TRUE;
3222  }
3223 
3224  /* round cut coefficients, i.e., subtract val from cutcoefs[j] */
3225  cutcoefs[j] = SCIPfeasFloor(scip, cutcoefs[j]);
3226 
3227  /* correct rhs */
3228  if ( ! SCIPisSumZero(scip, lbnd) )
3229  *cutrhs -= lbnd * val;
3230  }
3231  }
3232  }
3233  else
3234  {
3235  /* force coefficients of all continuous variables or of variables not in the lp to zero */
3236  assert( pos == -1 || mipdata->coltype[pos] == colContinuous || mipdata->coltype[pos] == colConverted );
3237 
3238  /* check whether all coefficients for continuous or converted variables are nonnegative */
3239  if ( pos >= 0 )
3240  {
3241  if ( SCIPisFeasNegative(scip, cutcoefs[j]) )
3242  {
3243  *success = FALSE;
3244  break;
3245  }
3246  }
3247 
3248  cutcoefs[j] = 0.0;
3249  }
3250  }
3251 
3252  /* round rhs */
3253  *cutrhs = SCIPfeasFloor(scip, *cutrhs);
3254 
3255  return SCIP_OKAY;
3256 }
3257 
3258 /** Create CG-cut directly from solution of sub-MIP */
3259 static
3260 SCIP_RETCODE createCGCutDirect(
3261  SCIP* scip, /**< SCIP data structure */
3262  SCIP_SEPA* sepa, /**< separator */
3263  SCIP_SEPADATA* sepadata, /**< separator data */
3264  CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
3265  SCIP_SOL* sol, /**< solution of sub-MIP */
3266  SCIP_Real* cutcoefs, /**< cut coefficients */
3267  int* cutinds, /**< problem indices of variables appearing in cut */
3268  SCIP_Real* cutvals, /**< values of variables in cut */
3269  SCIP_Real* varsolvals, /**< solution value of variables */
3270  SCIP_Real* weights, /**< weights to compute cmir cut */
3271  int* nprevrows, /**< number of previously generated rows */
3272  SCIP_ROW** prevrows, /**< previously generated rows */
3273  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
3274  unsigned int* ngen /**< number of generated cuts */
3275  )
3276 {
3277  char name[SCIP_MAXSTRLEN];
3278  SCIP_Bool cutislocal;
3279  SCIP_Bool localrowsused;
3280  SCIP_Bool localboundsused;
3281  SCIP_Real cutrhs;
3282  SCIP_Real cutact;
3283  SCIP_Bool success;
3284  SCIP_VAR** vars;
3285  int cutrank = 0;
3286  int nvars;
3287  int k;
3288 
3289  assert( scip != NULL );
3290  assert( sepadata != NULL );
3291  assert( mipdata != NULL );
3292  assert( sol != NULL );
3293  assert( cutcoefs != NULL );
3294  assert( cutinds != NULL );
3295  assert( cutvals != NULL );
3296  assert( varsolvals != NULL );
3297  assert( weights != NULL );
3298  assert( nprevrows != NULL );
3299  assert( prevrows != NULL );
3300  assert( cutoff != NULL );
3301  assert( ngen != NULL );
3302 
3303  /* get variable data */
3304  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3305 
3306  cutrhs = 0.0;
3307  localrowsused = FALSE;
3308  localboundsused = FALSE;
3309  *cutoff = FALSE;
3310  success = TRUE;
3311 
3312  /* compute coefficients */
3313  SCIP_CALL( computeCut(scip, sepa, mipdata, sepadata, sol, TRUE, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) );
3314  cutislocal = localrowsused || localboundsused;
3315 
3316  /* Take next solution if cut was not valid - this can easily happen for mixed-integer problems, see function computeCut(). */
3317  if ( ! success )
3318  {
3319  /* try again without using fractional value */
3320  SCIP_CALL( computeCut(scip, sepa, mipdata, sepadata, sol, FALSE, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) );
3321  cutislocal = localrowsused || localboundsused;
3322 
3323  if ( ! success )
3324  {
3325  SCIPdebugMsg(scip, "cut not valid - skipping ...\n");
3326  return SCIP_OKAY;
3327  }
3328  }
3329 
3330  /* compute activity */
3331  cutact = 0.0;
3332  for (k = 0; k < nvars; ++k)
3333  cutact += cutcoefs[k] * varsolvals[k];
3334 
3335 #ifdef SCIP_DISABLED_CODE
3336  /* the following test should be treated with care because of numerical differences - see computeCut() */
3337  {
3338  /* check for correctness of computed values */
3339  SCIP* subscip;
3340  SCIP_Real obj = 0.0;
3341  SCIP_Real val;
3342  SCIP_Bool contVarShifted = FALSE;
3343  unsigned int j;
3344  SCIP_COL** cols;
3345  int ncols;
3346 
3347  subscip = mipdata->subscip;
3348  assert( subscip != NULL );
3349 
3350  SCIP_CALL( SCIPprintSol(subscip, sol, NULL, FALSE) );
3351 
3352  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
3353  for (j = 0; j < mipdata->ncols; ++j)
3354  {
3355  if ( mipdata->coltype[j] == colPresent )
3356  {
3357  int idx;
3358  assert( mipdata->alpha[j] != NULL );
3359  val = SCIPgetSolVal(subscip, sol, mipdata->alpha[j]);
3360  assert( SCIPisFeasIntegral(subscip, val) );
3361  idx = SCIPvarGetProbindex(SCIPcolGetVar(cols[j]));
3362  assert( SCIPisFeasEQ(scip, val, cutcoefs[idx]) );
3363  obj += val * SCIPvarGetObj(mipdata->alpha[j]);
3364  }
3365  else
3366  {
3367  if ( (mipdata->coltype[j] == colContinuous || mipdata->coltype[j] == colConverted) && mipdata->isshifted[j] )
3368  contVarShifted = TRUE;
3369  }
3370  }
3371  assert( mipdata->beta != NULL );
3372  val = SCIPgetSolVal(subscip, sol, mipdata->beta);
3373  assert( SCIPisFeasIntegral(subscip, val) );
3374  obj += val * SCIPvarGetObj(mipdata->beta);
3375  assert( contVarShifted || SCIPisFeasEQ(scip, obj, cutact - cutrhs) );
3376  }
3377 #endif
3378 
3379  /* if successful, convert dense cut into sparse row, and add the row as a cut */
3380  if ( SCIPisFeasGT(scip, cutact, cutrhs) )
3381  {
3382  SCIP_Real cutnorm;
3383  int cutlen;
3384 
3385  /* store the cut as sparse row, calculate activity and norm of cut */
3386  SCIP_CALL( storeCutInArrays(scip, nvars, cutcoefs, varsolvals, mipdata->normtype,
3387  cutinds, cutvals, &cutlen, &cutact, &cutnorm) );
3388 
3389  SCIPdebugMsg(scip, "act=%f, rhs=%f, norm=%f, eff=%f\n", cutact, cutrhs, cutnorm, (cutact - cutrhs)/cutnorm);
3390 
3391  /* if norm is 0, the cut is trivial */
3392  if ( SCIPisPositive(scip, cutnorm) )
3393  {
3394  SCIP_Bool violated = SCIPisEfficacious(scip, (cutact - cutrhs)/cutnorm);
3395 
3396  if ( violated || (sepadata->usecutpool && ! cutislocal ) )
3397  {
3398  SCIP_ROW* cut;
3399 
3400  /* create the cut */
3401  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
3402  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
3403  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
3404 
3405  for (k = 0; k < cutlen; ++k)
3406  {
3407  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutvals[k]) );
3408  }
3409 
3410  /* set cut rank */
3411  SCIProwChgRank(cut, cutrank);
3412 
3413  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
3414 
3415  /*SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) );*/
3416 
3417  /* add cut to pool */
3418  if ( ! cutislocal )
3419  {
3420  assert( violated || sepadata->usecutpool );
3421  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
3422  }
3423 
3424  /* add cut if it is violated */
3425  if ( violated )
3426  {
3427  /* check whether cut has been found before - may happened due to projection */
3428  for (k = 0; k < *nprevrows; ++k)
3429  {
3430  SCIP_Real parval;
3431 
3432  assert( prevrows[k] != NULL );
3433  parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
3434  /* exit if row is parallel to existing cut and rhs is not better */
3435  if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
3436  break;
3437  }
3438 
3439  /* if cut is new */
3440  if ( k >= *nprevrows )
3441  {
3442  prevrows[*nprevrows] = cut;
3443  ++(*nprevrows);
3444 
3445  SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
3446  name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3447  SCIPgetCutEfficacy(scip, NULL, cut),
3448  SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
3449  SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
3450 #ifdef SCIP_DEBUG
3451  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3452 #else
3453  if ( sepadata->output )
3454  {
3455  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3456  }
3457 #endif
3458  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
3459  ++(*ngen);
3460  }
3461  else
3462  {
3463  SCIPdebugMsg(scip, "Cut already exists.\n");
3464  /* release the row */
3465  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3466  }
3467  }
3468  else
3469  {
3470  /* release the row */
3471  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3472  }
3473  }
3474  }
3475  }
3476 
3477  return SCIP_OKAY;
3478 }
3479 
3480 
3481 /** create CG-cut via CMIR-function */
3482 static
3483 SCIP_RETCODE createCGCutCMIR(
3484  SCIP* scip, /**< SCIP data structure */
3485  SCIP_SEPA* sepa, /**< separator */
3486  SCIP_SEPADATA* sepadata, /**< separator data */
3487  CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
3488  SCIP_SOL* sol, /**< solution of sub-MIP */
3489  SCIP_AGGRROW* aggrrow, /**< aggregation row to use for creating MIR cut */
3490  SCIP_Real* cutcoefs, /**< cut coefficients */
3491  int* cutinds, /**< problem indices of variables appearing in cut */
3492  SCIP_Real* cutvals, /**< values of variables in cut */
3493  SCIP_Real* varsolvals, /**< solution value of variables */
3494  SCIP_Real* weights, /**< weights to compute cmir cut */
3495  int* boundsfortrans, /**< bounds for cmir function of NULL */
3496  SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds for cmir function or NULL */
3497  int* nprevrows, /**< number of previously generated rows */
3498  SCIP_ROW** prevrows, /**< previously generated rows */
3499  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
3500  unsigned int* ngen /**< number of generated cuts */
3501  )
3502 {
3503  char name[SCIP_MAXSTRLEN];
3504  SCIP_Longint maxdnom;
3505  SCIP_Bool cutislocal;
3506  SCIP_Real maxscale;
3507  SCIP_Real cutrhs;
3508  SCIP_Real cutefficacy;
3509  SCIP_Bool success;
3510  SCIP_ROW** rows;
3511  SCIP_VAR** vars;
3512  SCIP* subscip;
3513  int nrows;
3514  int nvars;
3515  int k;
3516  int cutrank;
3517  int cutnnz;
3518 
3519  assert( scip != NULL );
3520  assert( sepadata != NULL );
3521  assert( mipdata != NULL );
3522  assert( sol != NULL );
3523  assert( cutcoefs != NULL );
3524  assert( cutinds != NULL );
3525  assert( cutvals != NULL );
3526  assert( varsolvals != NULL );
3527  assert( weights != NULL );
3528  assert( nprevrows != NULL );
3529  assert( prevrows != NULL );
3530  assert( cutoff != NULL );
3531  assert( ngen != NULL );
3532 
3533  *cutoff = FALSE;
3534  subscip = mipdata->subscip;
3535  assert( subscip != NULL );
3536 
3537  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
3538  assert( nrows > 0 );
3539  assert( (int) mipdata->nrows == nrows );
3540 
3541  /* @todo more advanced settings - compare sepa_gomory.c */
3542  maxdnom = (SCIP_Longint) sepadata->cutcoefbnd+1;
3543  maxscale = 10000.0;
3544 
3545  /* get variable data */
3546  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3547 
3548  /* generate weights */
3549  for (k = 0; k < nrows; ++k)
3550  {
3551  SCIP_Real val;
3552 
3553  weights[k] = 0;
3554  if ( mipdata->ylhs[k] != NULL )
3555  {
3556  assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3557 
3558  val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[k]);
3559  assert( ! SCIPisFeasNegative(subscip, val) );
3560 
3561  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3562  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3563 
3564  if ( SCIPisFeasPositive(subscip, val) )
3565  weights[k] = -val;
3566  }
3567 
3568  if ( mipdata->yrhs[k] != NULL )
3569  {
3570  assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3571 
3572  val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[k]);
3573  assert( ! SCIPisFeasNegative(subscip, val) );
3574 
3575  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3576  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3577 
3578  /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
3579  if ( SCIPisFeasGT(scip, val, ABS(weights[k])) )
3580  weights[k] = val;
3581  }
3582  }
3583 
3584  /* set up data for bounds to use */
3585  if ( sepadata->cmirownbounds )
3586  {
3587  int typefortrans;
3588 
3589  assert( boundsfortrans != NULL );
3590  assert( boundtypesfortrans != NULL );
3591 
3592  if ( sepadata->allowlocal )
3593  typefortrans = -2;
3594  else
3595  typefortrans = -1;
3596 
3597  /* check all variables */
3598  for (k = 0; k < nvars; ++k)
3599  {
3600  int pos;
3601  SCIP_VAR* var;
3602 
3603  var = vars[k];
3604  assert( var != NULL );
3605  pos = SCIPcolGetLPPos(SCIPvarGetCol(var));
3606 
3607  if ( pos < 0 )
3608  continue;
3609 
3610  assert( pos < (int) mipdata->ncols );
3611  assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
3612 
3613  boundsfortrans[k] = typefortrans;
3614  boundtypesfortrans[k] = SCIP_BOUNDTYPE_LOWER;
3615 
3616  if ( mipdata->coltype[pos] == colContinuous || mipdata->coltype[pos] == colConverted )
3617  {
3618  assert( SCIPvarIsIntegral(var) || mipdata->coltype[pos] != colContinuous );
3619  continue;
3620  }
3621 
3622  /* check upper bound */
3623  if ( mipdata->z[pos] != NULL && SCIPisSumPositive(subscip, SCIPgetSolVal(subscip, sol, mipdata->z[pos])) )
3624  {
3625  /* check whether variable is complemented */
3626  if ( ! mipdata->iscomplemented[pos] )
3627  boundtypesfortrans[k] = SCIP_BOUNDTYPE_UPPER;
3628  /* otherwise use lower bound */
3629  }
3630  else
3631  {
3632  /* check whether variable is complemented */
3633  if ( mipdata->iscomplemented[pos] )
3634  boundtypesfortrans[k] = SCIP_BOUNDTYPE_UPPER;
3635  /* otherwise use lower bound */
3636  }
3637  }
3638  }
3639 
3640  /* create a MIR cut using the above calculated weights */
3641  cutefficacy = -1.0;
3642  cutrhs = -1.0;
3643  SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, weights, NULL, -1, FALSE,
3644  sepadata->allowlocal, 2, (int) MAXAGGRLEN(nvars), &success) );
3645 
3646  if ( ! success )
3647  return SCIP_OKAY;
3648 
3649  SCIP_CALL( SCIPcalcMIR(scip, NULL, POSTPROCESS, BOUNDSWITCH, USEVBDS, sepadata->allowlocal, FIXINTEGRALRHS, boundsfortrans,
3650  boundtypesfortrans, MINFRAC, MAXFRAC, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy,
3651  &cutrank, &cutislocal, &success) );
3652 
3653  assert( sepadata->allowlocal || !cutislocal );
3654  SCIPdebugMsg(scip, "CMIR: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success,
3655  SCIPisEfficacious(scip, cutefficacy) ? " " : " not ", cutefficacy, cutrhs);
3656 
3657  /* If successful, convert dense cut into sparse row, and add the row as a cut only if the cut if violated - if it is
3658  * not violated we might store non-local cuts in the pool. */
3659  if ( success && (SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) )
3660  {
3661  SCIP_ROW* cut;
3662 
3663  /* create the cut */
3664  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
3665  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
3666 
3667  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
3668 
3669  for (k = 0; k < cutnnz; ++k)
3670  {
3671  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutcoefs[k]) );
3672  }
3673 
3674  assert( success );
3675 
3676  /* set cut rank */
3677  SCIProwChgRank(cut, cutrank);
3678 
3679 #ifdef SCIP_DEBUG
3680  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3681 #else
3682  if ( sepadata->output )
3683  {
3684  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3685  }
3686 #endif
3687 
3688  /* try to scale the cut to integral values */
3689  SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
3690  maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
3691 
3692  /* if the cut could be made integral */
3693  if ( success )
3694  {
3695  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
3696 
3697  /* add cut to pool */
3698  if ( ! cutislocal )
3699  {
3700  assert( SCIPisEfficacious(scip, cutefficacy) || sepadata->usecutpool );
3701  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
3702  }
3703 
3704  if ( ! SCIPisCutEfficacious(scip, NULL, cut) )
3705  {
3706  SCIPdebugMsg(scip, " -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
3707  name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3708  SCIPgetCutEfficacy(scip, NULL, cut));
3709 
3710  /* release the row */
3711  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3712  }
3713  else
3714  {
3715  /* check whether cut has been found before - may happend due to projection */
3716  for (k = 0; k < *nprevrows; ++k)
3717  {
3718  SCIP_Real parval;
3719 
3720  assert( prevrows[k] != NULL );
3721  parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
3722  /* exit if row is parallel to existing cut and rhs is not better */
3723  if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
3724  break;
3725  }
3726 
3727  /* if cut is new */
3728  if ( k >= *nprevrows )
3729  {
3730  prevrows[*nprevrows] = cut;
3731  ++(*nprevrows);
3732 
3733  SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n",
3734  name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3735  SCIPgetCutEfficacy(scip, NULL, cut), SCIProwGetRank(cut),
3736  SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
3737  SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
3738 #ifdef SCIP_OUTPUT
3739  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3740 #else
3741  if ( sepadata->output )
3742  {
3743  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3744  }
3745 #endif
3746  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
3747  ++(*ngen);
3748  }
3749  else
3750  {
3751  SCIPdebugMsg(scip, "Cut already exists.\n");
3752  /* release the row */
3753  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3754  }
3755  }
3756  }
3757  else
3758  {
3759  SCIPdebugMsg(scip, " -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n",
3760  name, cutefficacy, cutrhs);
3761 
3762  /* release the row */
3763  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3764  }
3765  }
3766 
3767  return SCIP_OKAY;
3768 }
3769 
3770 
3771 /** create CG-cut via strong-CG-function */
3772 static
3773 SCIP_RETCODE createCGCutStrongCG(
3774  SCIP* scip, /**< SCIP data structure */
3775  SCIP_SEPA* sepa, /**< separator */
3776  SCIP_SEPADATA* sepadata, /**< separator data */
3777  CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
3778  SCIP_SOL* sol, /**< solution of sub-MIP */
3779  SCIP_AGGRROW* aggrrow, /**< aggregation row to use for creating MIR cut */
3780  SCIP_Real* cutcoefs, /**< cut coefficients */
3781  int* cutinds, /**< problem indices of variables appearing in cut */
3782  SCIP_Real* cutvals, /**< values of variables in cut */
3783  SCIP_Real* varsolvals, /**< solution value of variables */
3784  SCIP_Real* weights, /**< weights to compute cmir cut */
3785  int* nprevrows, /**< number of previously generated rows */
3786  SCIP_ROW** prevrows, /**< previously generated rows */
3787  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
3788  unsigned int* ngen /**< number of generated cuts */
3789  )
3790 {
3791  char name[SCIP_MAXSTRLEN];
3792  SCIP_Longint maxdnom;
3793  SCIP_Bool cutislocal;
3794  SCIP_Real maxscale;
3795  SCIP_Real cutrhs;
3796  SCIP_Real cutefficacy;
3797  SCIP_Bool success;
3798  SCIP_ROW** rows;
3799  SCIP_VAR** vars;
3800  SCIP* subscip;
3801  int nrows;
3802  int nvars;
3803  int k;
3804  int cutrank;
3805  int cutnnz;
3806 
3807  assert( scip != NULL );
3808  assert( sepadata != NULL );
3809  assert( mipdata != NULL );
3810  assert( sol != NULL );
3811  assert( cutcoefs != NULL );
3812  assert( cutinds != NULL );
3813  assert( cutvals != NULL );
3814  assert( varsolvals != NULL );
3815  assert( weights != NULL );
3816  assert( nprevrows != NULL );
3817  assert( prevrows != NULL );
3818  assert( cutoff != NULL );
3819  assert( ngen != NULL );
3820 
3821  *cutoff = FALSE;
3822  subscip = mipdata->subscip;
3823  assert( subscip != NULL );
3824 
3825  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
3826  assert( nrows > 0 );
3827  assert( (int) mipdata->nrows == nrows );
3828 
3829  /* @todo more advanced settings - compare sepa_gomory.c */
3830  maxdnom = (SCIP_Longint) sepadata->cutcoefbnd + 1;
3831  maxscale = 10000.0;
3832 
3833  /* get variable data */
3834  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3835 
3836  /* generate weights */
3837  for (k = 0; k < nrows; ++k)
3838  {
3839  SCIP_Real val;
3840 
3841  weights[k] = 0;
3842  if ( mipdata->ylhs[k] != NULL )
3843  {
3844  assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3845 
3846  val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[k]);
3847  assert( ! SCIPisFeasNegative(subscip, val) );
3848 
3849  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3850  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3851 
3852  if ( SCIPisFeasPositive(subscip, val) )
3853  weights[k] = -val;
3854  }
3855 
3856  if ( mipdata->yrhs[k] != NULL )
3857  {
3858  assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3859 
3860  val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[k]);
3861  assert( ! SCIPisFeasNegative(subscip, val) );
3862 
3863  assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3864  val = SCIPfrac(scip, val); /* take fractional value if variable has no upper bounds */
3865 
3866  /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
3867  if ( SCIPisFeasGT(scip, val, ABS(weights[k])) )
3868  weights[k] = val;
3869  }
3870  }
3871 
3872  /* create a strong CG cut out of the weighted LP rows using the B^-1 row as weights */
3873  cutefficacy = -1.0;
3874  cutrhs = -1.0;
3875  SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, weights, NULL, -1, FALSE,
3876  sepadata->allowlocal, 1, (int) MAXAGGRLEN(nvars), &success) );
3877 
3878  if ( ! success )
3879  return SCIP_OKAY;
3880 
3881  SCIP_CALL( SCIPcalcStrongCG(scip, NULL, POSTPROCESS, BOUNDSWITCH, USEVBDS, sepadata->allowlocal, MINFRAC, MAXFRAC,
3882  1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
3883 
3884  assert( sepadata->allowlocal || !cutislocal );
3885  SCIPdebugMsg(scip, "Strong-CG: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success,
3886  SCIPisEfficacious(scip, cutefficacy) ? " " : " not ", cutefficacy, cutrhs);
3887 
3888  /* If successful, convert dense cut into sparse row, and add the row as a cut only if the cut if violated - if it is
3889  * not violated we might store non-local cuts in the pool. */
3890  if ( success && (SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) )
3891  {
3892  SCIP_ROW* cut;
3893 
3894  /* create the cut */
3895  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
3896  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
3897 
3898  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
3899 
3900  for (k = 0; k < cutnnz; ++k)
3901  {
3902  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutcoefs[k]) );
3903  }
3904 
3905  assert( success );
3906 
3907  /* set cut rank */
3908  SCIProwChgRank(cut, cutrank);
3909 
3910 #ifdef SCIP_DEBUG
3911  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3912 #else
3913  if ( sepadata->output )
3914  {
3915  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3916  }
3917 #endif
3918 
3919  /* try to scale the cut to integral values */
3920  SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
3921  maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
3922 
3923  /* if the cut could be made integral */
3924  if ( success )
3925  {
3926  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
3927 
3928  /* add cut to pool */
3929  if ( ! cutislocal )
3930  {
3931  assert( SCIPisEfficacious(scip, cutefficacy) || sepadata->usecutpool );
3932  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
3933  }
3934 
3935  if ( ! SCIPisCutEfficacious(scip, NULL, cut) )
3936  {
3937  SCIPdebugMsg(scip, " -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
3938  name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3939  SCIPgetCutEfficacy(scip, NULL, cut));
3940 
3941  /* release the row */
3942  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3943  }
3944  else
3945  {
3946  /* check whether cut has been found before - may happend due to projection */
3947  for (k = 0; k < *nprevrows; ++k)
3948  {
3949  SCIP_Real parval;
3950 
3951  assert( prevrows[k] != NULL );
3952  parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
3953  /* exit if row is parallel to existing cut and rhs is not better */
3954  if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
3955  break;
3956  }
3957 
3958  /* if cut is new */
3959  if ( k >= *nprevrows )
3960  {
3961  prevrows[*nprevrows] = cut;
3962  ++(*nprevrows);
3963 
3964  SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n",
3965  name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3966  SCIPgetCutEfficacy(scip, NULL, cut), SCIProwGetRank(cut),
3967  SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
3968  SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
3969 #ifdef SCIP_OUTPUT
3970  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3971 #else
3972  if ( sepadata->output )
3973  {
3974  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3975  }
3976 #endif
3977  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
3978  ++(*ngen);
3979  }
3980  else
3981  {
3982  SCIPdebugMsg(scip, "Cut already exists.\n");
3983  /* release the row */
3984  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3985  }
3986  }
3987  }
3988  else
3989  {
3990  SCIPdebugMsg(scip, " -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n",
3991  name, cutefficacy, cutrhs);
3992 
3993  /* release the row */
3994  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3995  }
3996  }
3997 
3998  return SCIP_OKAY;
3999 }
4000 
4001 
4002 /** Create CG-cuts from solutions of sub-MIP */
4003 static
4004 SCIP_RETCODE createCGCuts(
4005  SCIP* scip, /**< SCIP data structure */
4006  SCIP_SEPA* sepa, /**< separator */
4007  SCIP_SEPADATA* sepadata, /**< separator data */
4008  CGMIP_MIPDATA* mipdata, /**< data for sub-MIP */
4009  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
4010  unsigned int* ngen /**< number of generated cuts */
4011  )
4012 {
4013  SCIP_BOUNDTYPE* boundtypesfortrans;
4014  SCIP_STAGE stage;
4015  SCIP_AGGRROW* aggrrow = NULL;
4016  SCIP_Real* varsolvals;
4017  SCIP_Real* weights;
4018  int* cutinds;
4019  SCIP_Real* cutvals;
4020  SCIP_Real* cutcoefs;
4021  SCIP_ROW** prevrows;
4022  SCIP_SOL** sols;
4023  SCIP_VAR** vars;
4024  SCIP* subscip;
4025  int* boundsfortrans;
4026  int nprevrows;
4027  int ntotalrows;
4028  int nsols;
4029  int nvars;
4030  int k;
4031  int s;
4032 
4033  assert( scip != NULL );
4034  assert( sepadata != NULL );
4035  assert( mipdata != NULL );
4036  assert( cutoff != NULL );
4037  assert( ngen != NULL );
4038 
4039  subscip = mipdata->subscip;
4040  assert( subscip != NULL );
4041 
4042  *cutoff = FALSE;
4043  *ngen = 0;
4044 
4045  /* check if solving was successful and get solutions */
4046  stage = SCIPgetStage(subscip);
4047  if ( stage == SCIP_STAGE_SOLVING || stage == SCIP_STAGE_SOLVED )
4048  nsols = SCIPgetNSols(subscip);
4049  else
4050  nsols = 0;
4051 
4052  /* only if solutions have been found */
4053  if ( nsols == 0 )
4054  return SCIP_OKAY;
4055 
4056  SCIPdebugMsg(scip, "Generating CG-cuts from %d sols (cmir: %u, strong-cg: %u) ...\n", nsols, sepadata->usecmir, sepadata->usestrongcg);
4057 
4058  sols = SCIPgetSols(subscip);
4059 
4060  /* get variable data */
4061  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
4062 
4063  /* allocate temporary memory */
4064  assert(mipdata->ntotalrows <= INT_MAX);
4065  ntotalrows = (int)mipdata->ntotalrows;
4066  assert( ntotalrows >= SCIPgetNLPRows(scip) && ntotalrows <= SCIPgetNLPRows(scip) + 1 );
4067  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
4068  SCIP_CALL( SCIPallocBufferArray(scip, &varsolvals, nvars) );
4069  SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) );
4070  SCIP_CALL( SCIPallocBufferArray(scip, &cutvals, nvars) );
4071  SCIP_CALL( SCIPallocBufferArray(scip, &weights, ntotalrows) );
4072  SCIP_CALL( SCIPallocBufferArray(scip, &prevrows, 2 * nsols) );
4073 
4074  if ( sepadata->usecmir || sepadata->usestrongcg )
4075  {
4076  SCIP_CALL( SCIPaggrRowCreate(scip, &aggrrow) );
4077  }
4078 
4079  /* prepare arrays for bound information, if requested */
4080  if ( sepadata->usecmir && sepadata->cmirownbounds )
4081  {
4082  SCIP_CALL( SCIPallocBufferArray(scip, &boundsfortrans, nvars) );
4083  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypesfortrans, nvars) );
4084  }
4085  else
4086  {
4087  boundsfortrans = NULL;
4088  boundtypesfortrans = NULL;
4089  }
4090 
4091  /* get solution values */
4092  for (k = 0; k < nvars; ++k)
4093  {
4094  if ( SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_COLUMN )
4095  varsolvals[k] = SCIPvarGetLPSol(vars[k]);
4096  else
4097  varsolvals[k] = 0.0;
4098  }
4099 
4100  /* loop through solutions found */
4101  nprevrows = 0;
4102  for (s = 0; s < nsols; ++s)
4103  {
4104  SCIP_SOL* sol;
4105  sol = sols[s];
4106 
4107  /* generate cuts by the C-MIR and/or Strong-CG functions */
4108  if ( sepadata->usecmir )
4109  {
4110  SCIP_CALL( createCGCutCMIR(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights,
4111  boundsfortrans, boundtypesfortrans, &nprevrows, prevrows, cutoff, ngen) );
4112  }
4113 
4114  if ( sepadata->usestrongcg )
4115  {
4116  SCIP_CALL( createCGCutStrongCG(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights,
4117  &nprevrows, prevrows, cutoff, ngen) );
4118  }
4119 
4120  if ( ! sepadata->usecmir && ! sepadata->usestrongcg )
4121  {
4122  SCIP_CALL( createCGCutDirect(scip, sepa, sepadata, mipdata, sol, cutcoefs, cutinds, cutvals, varsolvals, weights,
4123  &nprevrows, prevrows, cutoff, ngen) );
4124 
4125  assert(! sepadata->usecmir && ! sepadata->usestrongcg);
4126  }
4127  }
4128  assert( nprevrows <= 2 * nsols );
4129  assert( sepadata->usecmir || nprevrows <= nsols );
4130  assert( sepadata->usestrongcg || nprevrows <= nsols );
4131 
4132  /* release rows */
4133  for (k = 0; k < nprevrows; ++k)
4134  {
4135  SCIP_CALL( SCIPreleaseRow(scip, &(prevrows[k])) );
4136  }
4137 
4138  if ( sepadata->usecmir || sepadata->usestrongcg )
4139  SCIPaggrRowFree(scip, &aggrrow);
4140 
4141  /* free temporary memory */
4142  SCIPfreeBufferArrayNull(scip, &boundsfortrans);
4143  SCIPfreeBufferArrayNull(scip, &boundtypesfortrans);
4144 
4145  SCIPfreeBufferArray(scip, &prevrows);
4146  SCIPfreeBufferArray(scip, &weights);
4147  SCIPfreeBufferArray(scip, &cutvals);
4148  SCIPfreeBufferArray(scip, &cutinds);
4149  SCIPfreeBufferArray(scip, &varsolvals);
4150  SCIPfreeBufferArray(scip, &cutcoefs);
4151 
4152  return SCIP_OKAY;
4153 }
4154 
4155 
4156 /** frees "subscip" data */
4157 static
4158 SCIP_RETCODE freeSubscip(
4159  SCIP* scip, /**< SCIP data structure */
4160  SCIP_SEPA* sepa, /**< separator data */
4161  CGMIP_MIPDATA* mipdata /**< data for sub-MIP */
4162  )
4163 {
4164  SCIP_SEPADATA* sepadata;
4165  unsigned int i, j;
4166  SCIP* subscip;
4167 
4168  assert( scip != NULL );
4169  assert( sepa != NULL );
4170  assert( mipdata != NULL );
4171 
4172  /* free separator data */
4173  sepadata = SCIPsepaGetData(sepa);
4174  assert( sepadata != NULL );
4175 
4176  SCIPdebugMsg(scip, "Freeing subscip ...\n");
4177 
4178  subscip = mipdata->subscip;
4179  assert( subscip != NULL );
4180 
4181  for (j = 0; j < mipdata->ncols; ++j)
4182  {
4183  if ( mipdata->coltype[j] == colPresent )
4184  {
4185  assert( mipdata->alpha[j] != NULL );
4186  SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->alpha[j])) );
4187  SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->fracalpha[j])) );
4188  }
4189  }
4190  SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->beta)) );
4191  SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->fracbeta)) );
4192 
4193  for (i = 0; i < mipdata->nrows; ++i)
4194  {
4195  if ( mipdata->ylhs[i] != NULL )
4196  {
4197  SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->ylhs[i])) );
4198  }
4199  if ( mipdata->yrhs[i] != NULL )
4200  {
4201  SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->yrhs[i])) );
4202  }
4203  }
4204 
4205  if ( sepadata->useobjub || sepadata->useobjlb )
4206  {
4207  if ( mipdata->yrhs[mipdata->nrows] )
4208  {
4209  SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->yrhs[mipdata->nrows])) );
4210  }
4211  if ( mipdata->ylhs[mipdata->nrows] )
4212  {
4213  SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->ylhs[mipdata->nrows])) );
4214  }
4215  }
4216 
4217  for (j = 0; j < mipdata->ncols; ++j)
4218  {
4219  if ( mipdata->z[j] != NULL )
4220  {
4221  SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->z[j])) );
4222  }
4223  }
4224 
4225  SCIP_CALL( SCIPfree(&(mipdata->subscip)) );
4226 
4227  SCIPfreeBlockMemoryArray(scip, &(mipdata->rhs), mipdata->ntotalrows);
4228  SCIPfreeBlockMemoryArray(scip, &(mipdata->lhs), mipdata->ntotalrows);
4229  SCIPfreeBlockMemoryArray(scip, &(mipdata->z), 2*mipdata->ncols); /*lint !e647*/
4230  SCIPfreeBlockMemoryArray(scip, &(mipdata->yrhs), mipdata->ntotalrows);
4231  SCIPfreeBlockMemoryArray(scip, &(mipdata->ylhs), mipdata->ntotalrows);
4232  SCIPfreeBlockMemoryArray(scip, &(mipdata->isshifted), mipdata->ncols);
4233  SCIPfreeBlockMemoryArray(scip, &(mipdata->iscomplemented), mipdata->ncols);
4234  SCIPfreeBlockMemoryArray(scip, &(mipdata->coltype), mipdata->ncols);
4235  SCIPfreeBlockMemoryArray(scip, &(mipdata->fracalpha), mipdata->ncols);
4236  SCIPfreeBlockMemoryArray(scip, &(mipdata->alpha), mipdata->ncols);
4237 
4238  return SCIP_OKAY;
4239 }
4240 
4241 
4242 /*
4243  * Callback methods
4244  */
4245 
4246 
4247 /** initialization method of separator (called after problem was transformed) */
4248 static
4249 SCIP_DECL_SEPAINIT(sepaInitCGMIP)
4250 {
4251  SCIP_SEPADATA* sepadata;
4252 
4253  sepadata = SCIPsepaGetData(sepa);
4254  assert(sepadata != NULL);
4255 
4256  /* create and initialize random number generator */
4257  SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, DEFAULT_RANDSEED, TRUE) );
4258 
4259  return SCIP_OKAY;
4260 }
4261 
4262 /** deinitialization method of separator (called before transformed problem is freed) */
4263 static
4264 SCIP_DECL_SEPAEXIT(sepaExitCGMIP)
4265 { /*lint --e{715}*/
4266  SCIP_SEPADATA* sepadata;
4267 
4268  sepadata = SCIPsepaGetData(sepa);
4269  assert(sepadata != NULL);
4270 
4271  SCIPfreeRandom(scip, &sepadata->randnumgen);
4272 
4273  return SCIP_OKAY;
4274 }
4275 
4276 /** copy method for separator plugins (called when SCIP copies plugins) */
4277 static
4278 SCIP_DECL_SEPACOPY(sepaCopyCGMIP)
4279 { /*lint --e{715}*/
4280  assert( scip != NULL );
4281  assert( sepa != NULL );
4282  assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
4283 
4284  /* call inclusion method of constraint handler */
4285  SCIP_CALL( SCIPincludeSepaCGMIP(scip) );
4286 
4287  return SCIP_OKAY;
4288 }
4289 
4290 
4291 /** destructor of separator to free user data (called when SCIP is exiting) */
4292 static
4293 SCIP_DECL_SEPAFREE(sepaFreeCGMIP)
4294 { /*lint --e{715}*/
4295  SCIP_SEPADATA* sepadata;
4296 
4297  assert( scip != NULL );
4298  assert( sepa != NULL );
4299  assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
4300 
4301  /* free separator data */
4302  sepadata = SCIPsepaGetData(sepa);
4303  assert( sepadata != NULL );
4304 
4305  SCIPfreeBlockMemory(scip, &sepadata);
4306 
4307  SCIPsepaSetData(sepa, NULL);
4308 
4309  return SCIP_OKAY;
4310 }
4311 
4312 
4313 /** LP solution separation method of separator */
4314 static
4315 SCIP_DECL_SEPAEXECLP(sepaExeclpCGMIP)
4316 { /*lint --e{715}*/
4317  SCIP_SEPADATA* sepadata;
4318  CGMIP_MIPDATA* mipdata;
4319 
4320  int ncalls;
4321  int ncols;
4322  int nrows;
4323  unsigned int ngen = 0;
4324  SCIP_Bool success;
4325  SCIP_Bool cutoff = FALSE;
4326 
4327  assert( scip != NULL );
4328  assert( sepa != NULL );
4329  assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
4330  assert( result != NULL );
4331 
4332  *result = SCIP_DIDNOTRUN;
4333 
4334  sepadata = SCIPsepaGetData(sepa);
4335  assert(sepadata != NULL);
4336 
4337  /* only call separator, if we are not close to terminating */
4338  if ( SCIPisStopped(scip) )
4339  return SCIP_OKAY;
4340 
4341  /* only call separator up to a maximum depth */
4342  if ( sepadata->maxdepth >= 0 && depth > sepadata->maxdepth )
4343  return SCIP_OKAY;
4344 
4345  /* only call separator a given number of times at each node */
4346  ncalls = SCIPsepaGetNCallsAtNode(sepa);
4347  if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
4348  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
4349  return SCIP_OKAY;
4350 
4351  /* only call separator, if an optimal LP solution is at hand */
4352  if ( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
4353  return SCIP_OKAY;
4354 
4355  /* skip separation if there are continuous variables, but only integers required */
4356  if ( SCIPgetNContVars(scip) > 0 && sepadata->onlyintvars )
4357  return SCIP_OKAY;
4358 
4359  /* only call separator, if there are fractional variables */
4360  if ( SCIPgetNLPBranchCands(scip) == 0 )
4361  return SCIP_OKAY;
4362 
4363  /* check for parameters */
4364  if ( ( sepadata->useobjub || sepadata->useobjlb ) && ( sepadata->usecmir || sepadata->usestrongcg ) )
4365  {
4366  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
4367  "WARNING - sepa_cgmip: Using objective function bounds and CMIR or Strong-CG functions is useless. Turning off usage of objective function bounds.\n");
4368  SCIP_CALL( SCIPsetBoolParam(scip, "separating/cgmip/useobjub", FALSE) );
4369  SCIP_CALL( SCIPsetBoolParam(scip, "separating/cgmip/useobjlb", FALSE) );
4370  }
4371  sepadata->allowlocal = allowlocal;
4372 
4373  /* get LP data */
4374  ncols = SCIPgetNLPCols(scip);
4375  nrows = SCIPgetNLPRows(scip);
4376  if ( ncols <= NCOLSTOOSMALL || nrows <= NROWSTOOSMALL )
4377  return SCIP_OKAY;
4378 
4379  /* determine whether we should run the separation based on a decision tree */
4380  if ( sepadata->decisiontree )
4381  {
4382  SCIP_Bool separate;
4383  SCIP_Real firstlptime;
4384 
4385  separate = FALSE;
4386  firstlptime = SCIPgetFirstLPTime(scip);
4387 
4388  if ( nrows <= 136 && firstlptime <= 0.05 && ncols <= 143 )
4389  separate = TRUE;
4390  else if ( nrows <= 136 && 0.05 < firstlptime && firstlptime <= 0.15 && ncols <= 143 )
4391  separate = TRUE;
4392  else if ( 136 < nrows && nrows <= 332 && ncols <= 143 )
4393  separate = TRUE;
4394  else if ( 136 < nrows && nrows <= 332 && 655 < ncols && ncols <= 1290 )
4395  separate = TRUE;
4396  else if ( 333 < nrows && nrows <= 874 && 0.15 < firstlptime && firstlptime <= 0.25 && 2614 < ncols && ncols <= 5141 )
4397  separate = TRUE;
4398  else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 143 < ncols && ncols <= 265 )
4399  separate = TRUE;
4400  else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 265 < ncols && ncols <= 654 )
4401  separate = TRUE;
4402  else if ( 875 < nrows && nrows <= 1676 && 0.05 < firstlptime && firstlptime <= 0.15 )
4403  separate = TRUE;
4404  else if ( 875 < nrows && nrows <= 1676 && 0.15 < firstlptime && firstlptime <= 0.25 && 1291 < ncols && ncols <= 2613 )
4405  separate = TRUE;
4406  else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 655 < ncols && ncols <= 1290 )
4407  separate = TRUE;
4408  else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 1291 < ncols && ncols <= 2613 )
4409  separate = TRUE;
4410  else if ( nrows > 8146 && firstlptime > 6.25 )
4411  separate = TRUE;
4412 
4413  if ( ! separate )
4414  {
4415  return SCIP_OKAY;
4416  }
4417  }
4418 
4419  /* preceed with separation */
4420  *result = SCIP_DIDNOTFIND;
4421 
4422  SCIPdebugMsg(scip, "separating CG-cuts via sub-MIPs: %d cols, %d rows\n", ncols, nrows);
4423 
4424  /* prepare data */
4425  SCIP_CALL( SCIPallocBlockMemory(scip, &mipdata) );
4426  mipdata->subscip = NULL;
4427  mipdata->alpha = NULL;
4428  mipdata->fracalpha = NULL;
4429  mipdata->beta = NULL;
4430  mipdata->fracbeta = NULL;
4431  mipdata->coltype = NULL;
4432  mipdata->iscomplemented = NULL;
4433  mipdata->isshifted = NULL;
4434  mipdata->ylhs = NULL;
4435  mipdata->yrhs = NULL;
4436  mipdata->z = NULL;
4437  mipdata->lhs = NULL;
4438  mipdata->rhs = NULL;
4439  mipdata->normtype = ' ';
4440 
4441  mipdata->conshdlrfullnorm = CONSHDLRFULLNORM;
4442  mipdata->scip = scip;
4443  mipdata->sepa = sepa;
4444  mipdata->sepadata = sepadata;
4445 
4446  /* get the type of norm to use for efficacy calculations */
4447  SCIP_CALL( SCIPgetCharParam(scip, "separating/efficacynorm", &mipdata->normtype) );
4448 
4449  /* create subscip */
4450  SCIP_CALL( createSubscip(scip, sepa, sepadata, mipdata) );
4451 
4452  /* set parameters */
4453  SCIP_CALL( subscipSetParams(sepadata, mipdata) );
4454 
4455  if ( ! SCIPisStopped(scip) )
4456  {
4457  /* solve subscip */
4458  SCIP_CALL( solveSubscip(scip, sepadata, mipdata, &success) );
4459 
4460  /* preceed if solution was successful */
4461  if ( success && ! SCIPisStopped(scip) )
4462  {
4463  SCIP_CALL( createCGCuts(scip, sepa, sepadata, mipdata, &cutoff, &ngen) );
4464  }
4465  }
4466 
4467  SCIP_CALL( freeSubscip(scip, sepa, mipdata) );
4468  SCIPfreeBlockMemory(scip, &mipdata);
4469 
4470  SCIPdebugMsg(scip, "Found %u CG-cuts.\n", ngen);
4471 
4472  if ( cutoff )
4473  *result = SCIP_CUTOFF;
4474  else if ( ngen > 0 )
4475  *result = SCIP_SEPARATED;
4476 
4477 #ifdef SCIP_OUTPUT
4478  /* SCIP_CALL( SCIPwriteLP(scip, "cuts.lp") ); */
4479  /* SCIP_CALL( SCIPwriteMIP(scip, "cuts.lp", FALSE, TRUE) ); */
4480 #endif
4481 
4482  return SCIP_OKAY;
4483 }
4484 
4485 /*
4486  * separator specific interface methods
4487  */
4488 
4489 /** creates the CGMIP MIR cut separator and includes it in SCIP */
4490 SCIP_RETCODE SCIPincludeSepaCGMIP(
4491  SCIP* scip /**< SCIP data structure */
4492  )
4493 {
4494  SCIP_SEPADATA* sepadata;
4495  SCIP_SEPA* sepa = NULL;
4496 
4497  /* create separator data */
4498  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
4499 
4500  /* include separator */
4501  SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
4502  SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpCGMIP, NULL, sepadata) );
4503  assert(sepa != NULL);
4504 
4505  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyCGMIP) );
4506  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeCGMIP) );
4507  SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitCGMIP) );
4508  SCIP_CALL( SCIPsetSepaExit(scip, sepa, sepaExitCGMIP) );
4509 
4510  /* add separator parameters */
4511  SCIP_CALL( SCIPaddIntParam(scip,
4512  "separating/" SEPA_NAME "/maxrounds",
4513  "maximal number of cgmip separation rounds per node (-1: unlimited)",
4514  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
4515 
4516  SCIP_CALL( SCIPaddIntParam(scip,
4517  "separating/" SEPA_NAME "/maxroundsroot",
4518  "maximal number of cgmip separation rounds in the root node (-1: unlimited)",
4519  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
4520 
4521  SCIP_CALL( SCIPaddIntParam(scip,
4522  "separating/" SEPA_NAME "/maxdepth",
4523  "maximal depth at which the separator is applied (-1: unlimited)",
4524  &sepadata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
4525 
4526  SCIP_CALL( SCIPaddBoolParam(scip,
4527  "separating/" SEPA_NAME "/decisiontree",
4528  "Use decision tree to turn separation on/off?",
4529  &sepadata->decisiontree, FALSE, DEFAULT_DECISIONTREE, NULL, NULL) );
4530 
4531  SCIP_CALL( SCIPaddRealParam(scip,
4532  "separating/" SEPA_NAME "/timelimit",
4533  "time limit for sub-MIP",
4534  &sepadata->timelimit, TRUE, DEFAULT_TIMELIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4535 
4536  SCIP_CALL( SCIPaddRealParam(scip,
4537  "separating/" SEPA_NAME "/memorylimit",
4538  "memory limit for sub-MIP",
4539  &sepadata->memorylimit, TRUE, DEFAULT_MEMORYLIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4540 
4541  SCIP_CALL( SCIPaddLongintParam(scip,
4542  "separating/" SEPA_NAME "/minnodelimit",
4543  "minimum number of nodes considered for sub-MIP (-1: unlimited)",
4544  &sepadata->minnodelimit, FALSE, DEFAULT_MINNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
4545 
4546  SCIP_CALL( SCIPaddLongintParam(scip,
4547  "separating/" SEPA_NAME "/maxnodelimit",
4548  "maximum number of nodes considered for sub-MIP (-1: unlimited)",
4549  &sepadata->maxnodelimit, FALSE, DEFAULT_MAXNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
4550 
4551  SCIP_CALL( SCIPaddRealParam(scip,
4552  "separating/" SEPA_NAME "/cutcoefbnd",
4553  "bounds on the values of the coefficients in the CG-cut",
4554  &sepadata->cutcoefbnd, TRUE, DEFAULT_CUTCOEFBND, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4555 
4556  SCIP_CALL( SCIPaddBoolParam(scip,
4557  "separating/" SEPA_NAME "/onlyactiverows",
4558  "Use only active rows to generate cuts?",
4559  &sepadata->onlyactiverows, FALSE, DEFAULT_ONLYACTIVEROWS, NULL, NULL) );
4560 
4561  SCIP_CALL( SCIPaddIntParam(scip,
4562  "separating/" SEPA_NAME "/maxrowage",
4563  "maximal age of rows to consider if onlyactiverows is false",
4564  &sepadata->maxrowage, FALSE, DEFAULT_MAXROWAGE, -1, INT_MAX, NULL, NULL) );
4565 
4566  SCIP_CALL( SCIPaddBoolParam(scip,
4567  "separating/" SEPA_NAME "/onlyrankone",
4568  "Separate only rank 1 inequalities w.r.t. CG-MIP separator?",
4569  &sepadata->onlyrankone, FALSE, DEFAULT_ONLYRANKONE, NULL, NULL) );
4570 
4571  SCIP_CALL( SCIPaddBoolParam(scip,
4572  "separating/" SEPA_NAME "/onlyintvars",
4573  "Generate cuts for problems with only integer variables?",
4574  &sepadata->onlyintvars, FALSE, DEFAULT_ONLYINTVARS, NULL, NULL) );
4575 
4576  SCIP_CALL( SCIPaddBoolParam(scip,
4577  "separating/" SEPA_NAME "/contconvert",
4578  "Convert some integral variables to be continuous to reduce the size of the sub-MIP?",
4579  &sepadata->contconvert, FALSE, DEFAULT_CONTCONVERT, NULL, NULL) );
4580 
4581  SCIP_CALL( SCIPaddRealParam(scip,
4582  "separating/" SEPA_NAME "/contconvfrac",
4583  "fraction of integral variables converted to be continuous (if contconvert)",
4584  &sepadata->contconvfrac, FALSE, DEFAULT_CONTCONVFRAC, 0.0, 1.0, NULL, NULL) );
4585 
4586  SCIP_CALL( SCIPaddIntParam(scip,
4587  "separating/" SEPA_NAME "/contconvmin",
4588  "minimum number of integral variables before some are converted to be continuous",
4589  &sepadata->contconvmin, FALSE, DEFAULT_CONTCONVMIN, -1, INT_MAX, NULL, NULL) );
4590 
4591  SCIP_CALL( SCIPaddBoolParam(scip,
4592  "separating/" SEPA_NAME "/intconvert",
4593  "Convert some integral variables attaining fractional values to have integral value?",
4594  &sepadata->intconvert, FALSE, DEFAULT_INTCONVERT, NULL, NULL) );
4595 
4596  SCIP_CALL( SCIPaddRealParam(scip,
4597  "separating/" SEPA_NAME "/intconvfrac",
4598  "fraction of frac. integral variables converted to have integral value (if intconvert)",
4599  &sepadata->intconvfrac, FALSE, DEFAULT_INTCONVFRAC, 0.0, 1.0, NULL, NULL) );
4600 
4601  SCIP_CALL( SCIPaddIntParam(scip,
4602  "separating/" SEPA_NAME "/intconvmin",
4603  "minimum number of integral variables before some are converted to have integral value",
4604  &sepadata->intconvmin, FALSE, DEFAULT_INTCONVMIN, -1, INT_MAX, NULL, NULL) );
4605 
4606  SCIP_CALL( SCIPaddBoolParam(scip,
4607  "separating/" SEPA_NAME "/skipmultbounds",
4608  "Skip the upper bounds on the multipliers in the sub-MIP?",
4609  &sepadata->skipmultbounds, FALSE, DEFAULT_SKIPMULTBOUNDS, NULL, NULL) );
4610 
4611  SCIP_CALL( SCIPaddBoolParam(scip,
4612  "separating/" SEPA_NAME "/objlone",
4613  "Should the objective of the sub-MIP minimize the l1-norm of the multipliers?",
4614  &sepadata->objlone, FALSE, DEFAULT_OBJLONE, NULL, NULL) );
4615 
4616  SCIP_CALL( SCIPaddRealParam(scip,
4617  "separating/" SEPA_NAME "/objweight",
4618  "weight used for the row combination coefficient in the sub-MIP objective",
4619  &sepadata->objweight, TRUE, DEFAULT_OBJWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4620 
4621  SCIP_CALL( SCIPaddBoolParam(scip,
4622  "separating/" SEPA_NAME "/objweightsize",
4623  "Weight each row by its size?",
4624  &sepadata->objweightsize, FALSE, DEFAULT_OBJWEIGHTSIZE, NULL, NULL) );
4625 
4626  SCIP_CALL( SCIPaddBoolParam(scip,
4627  "separating/" SEPA_NAME "/dynamiccuts",
4628  "should generated cuts be removed from the LP if they are no longer tight?",
4629  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
4630 
4631  SCIP_CALL( SCIPaddBoolParam(scip,
4632  "separating/" SEPA_NAME "/usecmir",
4633  "use CMIR-generator (otherwise add cut directly)?",
4634  &sepadata->usecmir, FALSE, DEFAULT_USECMIR, NULL, NULL) );
4635 
4636  SCIP_CALL( SCIPaddBoolParam(scip,
4637  "separating/" SEPA_NAME "/usestrongcg",
4638  "use strong CG-function to strengthen cut?",
4639  &sepadata->usestrongcg, FALSE, DEFAULT_USESTRONGCG, NULL, NULL) );
4640 
4641  SCIP_CALL( SCIPaddBoolParam(scip,
4642  "separating/" SEPA_NAME "/cmirownbounds",
4643  "tell CMIR-generator which bounds to used in rounding?",
4644  &sepadata->cmirownbounds, FALSE, DEFAULT_CMIROWNBOUNDS, NULL, NULL) );
4645 
4646  SCIP_CALL( SCIPaddBoolParam(scip,
4647  "separating/" SEPA_NAME "/usecutpool",
4648  "use cutpool to store CG-cuts even if the are not efficient?",
4649  &sepadata->usecutpool, FALSE, DEFAULT_USECUTPOOL, NULL, NULL) );
4650 
4651  SCIP_CALL( SCIPaddBoolParam(scip,
4652  "separating/" SEPA_NAME "/primalseparation",
4653  "only separate cuts that are tight for the best feasible solution?",
4654  &sepadata->primalseparation, FALSE, DEFAULT_PRIMALSEPARATION, NULL, NULL) );
4655 
4656  SCIP_CALL( SCIPaddBoolParam(scip,
4657  "separating/" SEPA_NAME "/earlyterm",
4658  "terminate separation if a violated (but possibly sub-optimal) cut has been found?",
4659  &sepadata->earlyterm, FALSE, DEFAULT_EARLYTERM, NULL, NULL) );
4660 
4661  SCIP_CALL( SCIPaddBoolParam(scip,
4662  "separating/" SEPA_NAME "/addviolationcons",
4663  "add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?",
4664  &sepadata->addviolationcons, FALSE, DEFAULT_ADDVIOLATIONCONS, NULL, NULL) );
4665 
4666  SCIP_CALL( SCIPaddBoolParam(scip,
4667  "separating/" SEPA_NAME "/addviolconshdlr",
4668  "add constraint handler to filter out violated cuts?",
4669  &sepadata->addviolconshdlr, FALSE, DEFAULT_ADDVIOLCONSHDLR, NULL, NULL) );
4670 
4671  SCIP_CALL( SCIPaddBoolParam(scip,
4672  "separating/" SEPA_NAME "/conshdlrusenorm",
4673  "should the violation constraint handler use the norm of a cut to check for feasibility?",
4674  &sepadata->conshdlrusenorm, FALSE, DEFAULT_CONSHDLRUSENORM, NULL, NULL) );
4675 
4676  SCIP_CALL( SCIPaddBoolParam(scip,
4677  "separating/" SEPA_NAME "/useobjub",
4678  "Use upper bound on objective function (via primal solution)?",
4679  &sepadata->useobjub, FALSE, DEFAULT_USEOBJUB, NULL, NULL) );
4680 
4681  SCIP_CALL( SCIPaddBoolParam(scip,
4682  "separating/" SEPA_NAME "/useobjlb",
4683  "Use lower bound on objective function (via primal solution)?",
4684  &sepadata->useobjlb, FALSE, DEFAULT_USEOBJLB, NULL, NULL) );
4685 
4686  SCIP_CALL( SCIPaddBoolParam(scip,
4687  "separating/" SEPA_NAME "/subscipfast",
4688  "Should the settings for the sub-MIP be optimized for speed?",
4689  &sepadata->subscipfast, FALSE, DEFAULT_SUBSCIPFAST, NULL, NULL) );
4690 
4691  SCIP_CALL( SCIPaddBoolParam(scip,
4692  "separating/" SEPA_NAME "/output",
4693  "Should information about the sub-MIP and cuts be displayed?",
4694  &sepadata->output, FALSE, DEFAULT_OUTPUT, NULL, NULL) );
4695 
4696  SCIP_CALL( SCIPaddBoolParam(scip,
4697  "separating/" SEPA_NAME "/genprimalsols",
4698  "Try to generate primal solutions from Gomory cuts?",
4699  &sepadata->genprimalsols, FALSE, DEFAULT_GENPRIMALSOLS, NULL, NULL) );
4700 
4701  return SCIP_OKAY;
4702 }
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:2194
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:2082
SCIPisFeasZero
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:845
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:8975
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:1763
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:979
NULL
#define NULL
Definition: def.h:267
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:780
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:380
SCIPgetNLPIterations
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:448
SCIPisFeasLT
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
SCIProwGetAge
int SCIProwGetAge(SCIP_ROW *row)
Definition: lp.c:17371
SCIProwGetOriginSepa
SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
Definition: lp.c:17476
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:3483
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:18079
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:288
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:17161
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIPisSumPositive
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:756
SCIP_DECL_CONSFREE
static SCIP_DECL_CONSFREE(consFreeViolatedCuts)
Definition: sepa_cgmip.c:508
SQR
#define SQR(x)
Definition: def.h:214
SCIPisPositive
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:570
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
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:17351
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:1250
SCIPisFeasNegative
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:869
SCIProwGetNLPNonz
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:17227
FIXINTEGRALRHS
#define FIXINTEGRALRHS
Definition: sepa_cgmip.c:172
SCIP_DECL_SEPAINIT
static SCIP_DECL_SEPAINIT(sepaInitCGMIP)
Definition: sepa_cgmip.c:4249
SCIPgetVarsData
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
DEFAULT_INTCONVMIN
#define DEFAULT_INTCONVMIN
Definition: sepa_cgmip.c:132
SCIPgetSols
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2119
SCIProwGetLhs
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
FALSE
#define FALSE
Definition: def.h:94
CONSHDLR_NAME
#define CONSHDLR_NAME
Definition: sepa_cgmip.c:281
SCIPsetSubscipDepth
void SCIPsetSubscipDepth(SCIP *scip, int newdepth)
Definition: scip_copy.c:2626
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:17072
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:16973
SCIPgetSubscipDepth
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2605
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:181
SCIProwGetBasisStatus
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:17340
SCIPcolGetObj
SCIP_Real SCIPcolGetObj(SCIP_COL *col)
Definition: lp.c:16953
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:510
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
SCIPisNegative
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:582
TRUE
#define TRUE
Definition: def.h:93
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:601
SCIPsetPresolving
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
SCIP_RandNumGen
Definition: struct_misc.h:268
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17769
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:941
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Sepa
Definition: struct_sepa.h:46
SCIP_LONGINT_MAX
#define SCIP_LONGINT_MAX
Definition: def.h:159
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:307
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:744
scip_sepa.h
public methods for separator plugins
SCIPprintStatistics
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip_solvingstats.c:4190
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:2172
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:137
SCIPgetRowMaxCoef
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1922
SCIPfeasCeil
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:917
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:905
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:1067
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:18089
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:1242
SCIPcolGetPrimsol
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16996
SCIPsolve
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2486
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:1904
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:2770
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:458
SCIPcolGetRows
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17151
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:17401
SCIPgetDualbound
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip_solvingstats.c:1349
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:498
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:16963
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:372
SCIProwIsIntegral
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:17391
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:4219
DEFAULT_MAXROWAGE
#define DEFAULT_MAXROWAGE
Definition: sepa_cgmip.c:124
SCIP_DECL_SEPAEXECLP
static SCIP_DECL_SEPAEXECLP(sepaExeclpCGMIP)
Definition: sepa_cgmip.c:4315
DEFAULT_CONSHDLRUSENORM
#define DEFAULT_CONSHDLRUSENORM
Definition: sepa_cgmip.c:146
REALABS
#define REALABS(x)
Definition: def.h:197
SCIPvarGetLPSol
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18453
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:380
colConverted
Definition: sepa_cgmip.c:231
SCIPgetLowerbound
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip_solvingstats.c:1376
SCIPisFeasGT
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIPsetEmphasis
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip_param.c:882
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
subscipSetParams
static SCIP_RETCODE subscipSetParams(SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:2050
SCIProwGetRhs
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
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:1993
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:17411
SCIProwGetCols
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17238
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:4490
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:3879
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:1077
SCIProwGetVals
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17248
SCIP_VERBLEVEL_NORMAL
Definition: type_message.h:55
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:3773
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
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:2127
SCIP_DECL_SEPAEXIT
static SCIP_DECL_SEPAEXIT(sepaExitCGMIP)
Definition: sepa_cgmip.c:4264
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:1422
SCIP_PARAMEMPHASIS_FEASIBILITY
Definition: type_paramset.h:74
SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
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:3050
SCIPaddPoolCut
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
MIN
#define MIN(x, y)
Definition: def.h:243
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:17927
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:2070
SCIP_DECL_SEPACOPY
static SCIP_DECL_SEPACOPY(sepaCopyCGMIP)
Definition: sepa_cgmip.c:4278
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:17790
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:2443
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:2220
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:521
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:2743
colPresent
Definition: sepa_cgmip.c:229
SCIP_DECL_SEPAFREE
static SCIP_DECL_SEPAFREE(sepaFreeCGMIP)
Definition: sepa_cgmip.c:4293
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIPrandomGetReal
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
scip_lp.h
public methods for the LP relaxation, rows and columns
SCIProwGetRank
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:17381
DEFAULT_USESTRONGCG
#define DEFAULT_USESTRONGCG
Definition: sepa_cgmip.c:139
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:174
SCIProwGetParallelism
SCIP_Real SCIProwGetParallelism(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
Definition: lp.c:7724
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:17939
SCIP_LONGINT_FORMAT
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
SCIProwGetConstant
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17258
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:1562
freeSubscip
static SCIP_RETCODE freeSubscip(SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata)
Definition: sepa_cgmip.c:4158
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
MAX
#define MAX(x, y)
Definition: def.h:239
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:2169
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
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:2287
SCIPisIntegral
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:594
SCIPcolGetVar
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
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:1668
scip_randnumgen.h
public methods for random numbers
SCIProwChgRank
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17534
SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
SCIPreleaseCons
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
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:857
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:17539
SCIProwGetLPPos
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17501
SCIP_Real
#define SCIP_Real
Definition: def.h:173
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:718
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:193
SCIPaggrRowCreate
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1731
SCIPprintRow
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
SCIP_Longint
#define SCIP_Longint
Definition: def.h:158
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:667
SCIPcheckCopyLimits
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3253
SCIP_STAGE_SOLVING
Definition: type_set.h:53
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
SEPA_FREQ
#define SEPA_FREQ
Definition: sepa_cgmip.c:109
SCIPtransformProb
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:222
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:558
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:2309
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:18145
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
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:3260
SCIPwriteParams
SCIP_RETCODE SCIPwriteParams(SCIP *scip, const char *filename, SCIP_Bool comments, SCIP_Bool onlychanged)
Definition: scip_param.c:813
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:151
SCIPgetUpperbound
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip_solvingstats.c:1556
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:4004
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:130
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:213
SCIPgetNLPs
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip_solvingstats.c:429
scip_prob.h
public methods for global and local (sub)problems
SCIPcolGetNLPNonz
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:17140
SCIPvarIsIntegral
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17611
SCIPcolGetLPPos
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:17093
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:1844
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
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:17268
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:904
SCIPfloor
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:631
ABS
#define ABS(x)
Definition: def.h:235
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:339
SCIPcreateSol
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
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:1631
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71