Scippy

SCIP

Solving Constraint Integer Programs

sepa_gmi.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* This file was written by Giacomo Nannicini, */
15 /* Copyright (C) 2012 Singapore University of Technology and Design */
16 /* */
17 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
18 
19 /**@file sepa_gmi.c
20  * @brief Gomory Mixed-Integer Cuts
21  * @author Giacomo Nannicini
22  * @author Marc Pfetsch
23  *
24  * This file implements a Gomory Mixed-Integer (GMI) cuts generator that reads cuts from the simplex tableau, applying
25  * the textbook formula:
26  * \f[
27  * \sum_{j \in J_I : f_j \leq f_0} f_j x_j + \sum_{j \in J_I : f_j > f_0} f_0 \frac{1-f_j}{1 - f_0} x_j +
28  * \sum_{j \in J_C : a_j \geq 0} a_j x_j - \sum_{j \in J_C : a_j < 0} f_0 \frac{a_j}{1-f_0} x_j \geq f_0.
29  * \f]
30  * Here, \f$J_I\f$ and \f$J_C \subseteq \{1, \ldots, n\}\f$ are the indices of integer and continuous non basic
31  * variables, respectively. The tableaux row is given by \f$a_j\f$ and its right hand side is \f$a_0\f$. The values
32  * \f$f_j\f$ for \f$j = 0, \ldots, n\f$ denote the fractional values of the tableaux row and rhs, i.e., \f$f_j = a_j -
33  * \lfloor a_j \rfloor\f$.
34  *
35  * Here is a brief description of the simplex tableau that we can expect from the SCIP LP interfaces:
36  *
37  * - Nonbasic columns can be at the lower or upper bound, or they can be nonbasic at zero if they are free. Nonbasic columns
38  * at the upper bound must be flipped. Nonbasic free variables at zero are currently untested in the cut generator,
39  * but they should be handled properly anyway.
40  *
41  * - Nonbasic rows can be at lower or upper bound, depending on whether the lower or upper bound of the row is
42  * attained. SCIP always adds slack/surplus variables with a coefficient of +1: the slack variable is nonnegative in
43  * case of a <= constraint, it is nonpositive in case of a >= or ranged constraint. Therefore, slack variables
44  * corresponding to >= or ranged constraints must be flipped if the row is at its lower bound. (Ranged constraints at
45  * the upper bound do not have to be flipped, because the variable is nonpositive.)
46  *
47  * Generated cuts are modified and their numerical properties are checked before being added to the LP relaxation.
48  * Default parameters for cut modification and checking procedures are taken from the paper
49  *
50  * G. Cornuejols, F. Margot, and G. Nannicini:@n
51  * On the safety of Gomory cut generators.@n
52  * Mathematical Programming Computation 5, No. 4 (2013), pp. 345-395.
53  *
54  * In addition to the routines described in the paper above, here we additionally check the support of the cutting
55  * plane.
56  *
57  * @todo Check whether it is worth rescaling the cut to have integral coefficients on integer variables. This may lead
58  * to an integral slack variable, that has stronger cut coefficients in subsequent rounds.
59  */
60 
61 
62 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
63 
64 #include <assert.h>
65 #include <string.h>
66 
67 #include "scip/pub_misc.h"
68 #include "sepa_gmi.h"
69 
70 #define SEPA_NAME "gmi"
71 #define SEPA_DESC "Gomory Mixed-Integer cuts separator"
72 #define SEPA_PRIORITY -1000
73 #define SEPA_FREQ 0
74 #define SEPA_MAXBOUNDDIST 0.0
75 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
76 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
77 
78 #define DEFAULT_MAXROUNDS 5 /**< maximal number of GMI separation rounds per node (-1: unlimited) */
79 #define DEFAULT_MAXROUNDSROOT 30 /**< maximal number of GMI separation rounds in the root node (-1: unlimited) */
80 #define DEFAULT_MAXSEPACUTS -1 /**< maximal number of GMI cuts separated per separation round */
81 #define DEFAULT_MAXSEPACUTSROOT -1 /**< maximal number of GMI cuts separated per separation round in root node */
82 #define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
83 #define DEFAULT_SEPARATEROWS TRUE /**< separate rows with integral slack? */
84 
85 #define DEFAULT_AWAY 0.005 /**< minimal fractionality of a basic variable in order to try GMI cut - default */
86 #define DEFAULT_MIN_VIOLATION 0.00 /**< minimal violation to accept cut - default */
87 #define DEFAULT_EPS_COEFF 1e-11 /**< tolerance for zeroing out small coefficients - default */
88 #define DEFAULT_EPS_RELAX_ABS 1e-11 /**< absolute cut rhs relaxation - default */
89 #define DEFAULT_EPS_RELAX_REL 1e-13 /**< relative cut rhs relaxation - default */
90 #define DEFAULT_MAX_DYN 1.0e+6 /**< maximal valid range max(|weights|)/min(|weights|) of cut coefficients - default */
91 #define DEFAULT_MAX_SUPP_ABS 1000 /**< maximum cut support - absolute value in the formula - default */
92 #define DEFAULT_MAX_SUPP_REL 0.1 /**< maximum cut support - relative value in the formula - default */
93 
94 
95 /** separator data */
96 struct SCIP_SepaData
97 {
98  int maxrounds; /**< maximal number of GMI separation rounds per node (-1: unlimited) */
99  int maxroundsroot; /**< maximal number of GMI separation rounds in the root node (-1: unlimited) */
100  int maxsepacuts; /**< maximal number of GMI cuts separated per separation round */
101  int maxsepacutsroot; /**< maximal number of GMI cuts separated per separation round in root node */
102  int lastncutsfound; /**< total number of cuts found after last call of separator */
103  SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
104  SCIP_Bool separaterows; /**< separate rows with integral slack? */
105  SCIP_Real away; /**< minimal fractionality of a basis variable in order to try GMI cut */
106  SCIP_Real minviolation; /**< minimal violation to accept cut */
107  SCIP_Real epscoeff; /**< tolerance for zeroing out small coefficients */
108  SCIP_Real epsrelaxabs; /**< absolute cut rhs relaxation */
109  SCIP_Real epsrelaxrel; /**< relative cut rhs relaxation */
110  SCIP_Real maxdynamism; /**< maximal valid range max(|weights|)/min(|weights|) of cut coefficients */
111  int maxsuppabs; /**< maximum cut support - absolute value in the formula */
112  SCIP_Real maxsupprel; /**< maximum cut support - relative value in the formula */
113 };
114 
115 
116 /*
117  * local methods
118  */
119 
120 /** Modify the cut to make it numerically safer, and packs it from dense format to sparse format.
121  *
122  * See paper "On the safety of Gomory cut generators" by Cornuejols, Margot, and Nannicini for more information. Returns
123  * TRUE if cut is accepted, FALSE if it is discarded.
124  */
125 static
127  SCIP* scip, /**< pointer to the SCIP environment */
128  SCIP_SEPADATA* sepadata, /**< pointer to separator data */
129  int ncols, /**< number of columns in the LP */
130  SCIP_COL** cols, /**< columns of the LP */
131  SCIP_Real* densecoefs, /**< cut in dense format on input */
132  SCIP_Real* sparsecoefs, /**< cut coefficients in sparse format on output */
133  int* cutind, /**< cut indices in sparse format on output */
134  int* cutnz, /**< pointer to store the number of nonzero elements in the cut in sparse format on output */
135  SCIP_Real* cutrhs /**< pointer to store the rhs of the cut, initialized to original value, modified */
136  )
137 {
138  SCIP_COL* col;
139  int i;
140  int c;
141 
142  assert(scip != NULL);
143  assert(cols != NULL);
144  assert(densecoefs != NULL);
145  assert(sparsecoefs != NULL);
146  assert(cutind != NULL);
147  assert(cutnz != NULL);
148  assert(cutrhs != NULL);
149 
150  *cutnz = 0; /* this is the current position in the cut array */
151 
152  /* Check each cut coefficient. If it is small, try set it to zero. */
153  for( c = 0; c < ncols; ++c )
154  {
155  col = cols[c];
156  assert(col != NULL);
157  i = SCIPcolGetLPPos(col);
158  assert( 0 <= i );
159 
160  /* Cycle over small elements that are not zero. If the element is zero, it will be discarded anyway. */
161  if( EPSZ(densecoefs[i], sepadata->epscoeff) && ! SCIPisZero(scip, densecoefs[i]) )
162  {
163  if( densecoefs[i] > 0.0 )
164  {
165  /* If we would have to modify the rhs by a multiple of infinity, discard the cut altogether. */
166  if( SCIPisInfinity(scip, -SCIPcolGetLb(col)) )
167  return FALSE;
168 
169  /* Zero out coefficient and modify rhs to preserve validity and possibly strengthen the cut. */
170  *cutrhs -= densecoefs[i] * SCIPcolGetLb(cols[c]);
171  }
172  else if( densecoefs[i] < 0.0 )
173  {
174  /* If we would have to modify the rhs by a multiple of infinity, discard the cut altogether. */
175  if( SCIPisInfinity(scip, SCIPcolGetUb(col)) )
176  return FALSE;
177 
178  /* Zero out coefficient and modify rhs to preserve validity and possibly strengthen the cut. */
179  *cutrhs -= densecoefs[i] * SCIPcolGetUb(cols[c]);
180  }
181  } /* if( EPSZ(densecoefs[i], sepadata->epscoeff) && ! SCIPisZero(densecoefs[i]) ) */
182  else if( ! EPSZ(densecoefs[i], sepadata->epscoeff) )
183  {
184  /* cut coefficient is large enough - keep it and write in sparse form */
185  sparsecoefs[*cutnz] = densecoefs[i];
186  cutind[*cutnz] = c;
187  (*cutnz)++;
188  }
189  } /* for( c = 0; c < ncols; ++c ) */
190 
191  /* Relax rhs of the cut */
192  *cutrhs += REALABS(*cutrhs) * sepadata->epsrelaxrel + sepadata->epsrelaxabs;
193 
194  return (*cutnz > 0) ? TRUE : FALSE;
195 }
196 
197 /** Check the numerical properties of the cut.
198  *
199  * See paper "On the safety of Gomory cut generators" by Cornuejols, Margot, and Nannicini for more information. Returns
200  * TRUE if cut is accepted, FALSE if it is discarded.
201  */
202 static
204  SCIP* scip, /**< pointer to the SCIP environment */
205  SCIP_SEPADATA* sepadata, /**< pointer to separator data */
206  int ncols, /**< number of columns in the LP */
207  SCIP_COL** cols, /**< columns of the LP */
208  SCIP_Real* cutcoefs, /**< cut in sparse format */
209  int* cutind, /**< cut indices in sparse format */
210  int cutnz, /**< number of nonzero elements in the cut in sparse format */
211  SCIP_Real cutrhs, /**< rhs of the cut */
212  SCIP_Real* cutact /**< pointer to store activity of the cut at the current LP optimum will go here on output */
213  )
214 {
215  SCIP_Real violation;
216  SCIP_Real mincoef;
217  SCIP_Real maxcoef;
218  int i;
219 
220  assert(scip != NULL);
221  assert(cols != NULL);
222  assert(cutcoefs != NULL);
223  assert(cutind != NULL);
224  assert(cutact != NULL);
225  assert(cutnz > 0);
226 
227  /* Check maximum support */
228  if( cutnz > ncols * sepadata->maxsupprel + sepadata->maxsuppabs )
229  {
230  SCIPdebugMsg(scip, "Cut too dense (%d > %d).\n", cutnz, (int) (ncols * sepadata->maxsupprel + sepadata->maxsuppabs));
231  return FALSE;
232  }
233 
234  /* Compute cut violation and dynamism */
235  mincoef = SCIP_REAL_MAX;
236  maxcoef = 0.0;
237  *cutact = 0.0;
238 
239  for( i = 0; i < cutnz; ++i )
240  {
241  mincoef = MIN(mincoef, REALABS(cutcoefs[i])); /*lint !e666*/
242  maxcoef = MAX(maxcoef, REALABS(cutcoefs[i])); /*lint !e666*/
243  *cutact += cutcoefs[i] * SCIPcolGetPrimsol(cols[cutind[i]]);
244  }
245 
246  /* Check dynamism */
247  if( maxcoef > mincoef * sepadata->maxdynamism )
248  {
249  SCIPdebugMsg(scip, "Cut too dynamic (%g > %g).\n", maxcoef, mincoef * sepadata->maxdynamism);
250  return FALSE;
251  }
252 
253  /* Check minimum violation */
254  violation = *cutact - cutrhs;
255  if( REALABS(cutrhs) > 1.0 )
256  violation /= REALABS(cutrhs);
257 
258  return (violation >= sepadata->minviolation) ? TRUE : FALSE;
259 }
260 
261 /** Method to obtain a GMI in the space of the original variables from a row of the simplex tableau.
262  *
263  * Returns TRUE if cut is successfully created, FALSE if no cut was generated or if it should be discarded. If the
264  * function returns FALSE, the contents of cutcoefs, cutind, cutnz, cutrhs, cutact may be garbage.
265  */
266 static
268  SCIP* scip, /**< pointer to the SCIP environment */
269  SCIP_SEPADATA* sepadata, /**< pointer to separator data */
270  int ncols, /**< number of columns in the LP */
271  int nrows, /**< number of rows in the LP */
272  SCIP_COL** cols, /**< columns of the LP */
273  SCIP_ROW** rows, /**< rows of the LP */
274  SCIP_Real* binvrow, /**< row of the basis inverse */
275  SCIP_Real* binvarow, /**< row of the simplex tableau */
276  SCIP_Real rowrhs, /**< rhs of the tableau row, i.e., corresponding element in the LP solution */
277  SCIP_Real* cutcoefs, /**< array for cut elements in sparse format - must be of size ncols */
278  int* cutind, /**< array for indices of nonzero cut coefficients - must be of size ncols */
279  int* cutnz, /**< pointer to store number of nonzero elements in the cut */
280  SCIP_Real* cutrhs, /**< pointer to store cut rhs */
281  SCIP_Real* cutact, /**< pointer to store cut activity at the current LP optimum - only meaningful if returns TRUE */
282  SCIP_Real* workcoefs /**< working array of size ncols, allocated by caller for efficiency */
283  )
284 {
285  SCIP_COL* col;
286  SCIP_ROW* row;
287  SCIP_Real rowelem;
288  SCIP_Real cutelem;
289  SCIP_Real f0;
290  SCIP_Real ratiof0compl;
291  SCIP_Bool success;
292  int i;
293  int c;
294 
295  assert(scip != NULL);
296  assert(cols != NULL);
297  assert(rows != NULL);
298  assert(binvrow != NULL);
299  assert(binvarow != NULL);
300  assert(cutcoefs != NULL);
301  assert(cutind != NULL);
302  assert(cutnz != NULL);
303  assert(cutrhs != NULL);
304  assert(cutact != NULL);
305  assert(workcoefs != NULL);
306 
307  /* Compute cut fractionality f0 and f0/(1-f0). */
308  f0 = SCIPfeasFrac(scip, rowrhs);
309  ratiof0compl = f0/(1-f0);
310 
311  /* rhs of the cut is the fractional part of the LP solution for the basic variable */
312  *cutrhs = -f0;
313 
314  /* clear cutcoefs */
315  BMSclearMemoryArray(workcoefs, ncols);
316 
317  /* Generate cut coefficients for the original variables. We first use workcoefs to store the cut in dense form, then
318  * we clean and pack the cut to sparse form in cutcoefs. */
319  for( c = 0; c < ncols; ++c)
320  {
321  col = cols[c];
322  assert( col != NULL );
323 
324  /* Get simplex tableau element. */
325  switch ( SCIPcolGetBasisStatus(col) )
326  {
327  case SCIP_BASESTAT_LOWER:
328  /* Take element if nonbasic at lower bound. */
329  rowelem = binvarow[c];
330  break;
331  case SCIP_BASESTAT_UPPER:
332  /* Flip element if nonbasic at upper bound. */
333  rowelem = -binvarow[c];
334  break;
335  case SCIP_BASESTAT_ZERO:
336  /* Nonbasic free variable at zero: cut coefficient is zero, skip */
337  continue;
338  case SCIP_BASESTAT_BASIC:
339  default:
340  /* Basic variable: skip */
341  continue;
342  }
343 
344  /* Integer variables */
345  if( SCIPcolIsIntegral(col) )
346  {
347  /* If cutelem < 0, then we know SCIPisZero(scip, cutelem) is true and hope it doesn't do much damage. */
348  cutelem = SCIPfrac(scip, rowelem);
349 
350  if( cutelem > f0 )
351  {
352  /* cut element if f > f0 */
353  cutelem = -((1.0 - cutelem) * ratiof0compl);
354  }
355  else
356  {
357  /* cut element if f <= f0 */
358  cutelem = -cutelem;
359  }
360  }
361  /* Continuous variables */
362  else
363  {
364  if( rowelem < 0.0 )
365  {
366  /* cut element if f < 0 */
367  cutelem = rowelem * ratiof0compl;
368  }
369  else
370  {
371  /* cut element if f >= 0 */
372  cutelem = -rowelem;
373  }
374  }
375 
376  if( ! SCIPisZero(scip, cutelem) )
377  {
378  /* Unflip if necessary, and adjust rhs if at lower or upper bound. */
380  {
381  cutelem = -cutelem;
382  *cutrhs += cutelem * SCIPcolGetUb(col);
383  }
384  else
385  *cutrhs += cutelem * SCIPcolGetLb(col);
386 
387  /* Add coefficient to cut in dense form. */
388  workcoefs[SCIPcolGetLPPos(col)] = cutelem;
389  }
390  } /* for( c = 0; c < ncols; ++c) */
391 
392  /* Generate cut coefficients for the slack variables. */
393  for( c = 0; c < nrows; ++c )
394  {
395  row = rows[c];
396  assert( row != NULL );
397 
398  /* Get simplex tableau element. */
399  switch ( SCIProwGetBasisStatus(row) )
400  {
401  case SCIP_BASESTAT_LOWER:
402  /* Take element if nonbasic at lower bound. */
403  rowelem = binvrow[SCIProwGetLPPos(row)];
404  /* But if this is a >= or ranged constraint at the lower bound, we have to flip the row element. */
405  if( !SCIPisInfinity(scip, -SCIProwGetLhs(row)) )
406  rowelem = -rowelem;
407  break;
408  case SCIP_BASESTAT_UPPER:
409  /* Take element if nonbasic at upper bound - see notes at beginning of file: only nonpositive slack variables
410  * can be nonbasic at upper, therefore they should be flipped twice and we can take the element directly. */
411  rowelem = binvrow[SCIProwGetLPPos(row)];
412  break;
413  case SCIP_BASESTAT_ZERO:
414  /* Nonbasic free variable at zero: cut coefficient is zero, skip */
415  SCIPdebugMsg(scip, "Free nonbasic slack variable, this should not happen!\n");
416  continue;
417  case SCIP_BASESTAT_BASIC:
418  default:
419  /* Basic variable: skip */
420  continue;
421  }
422 
423  /* Check if row is integral and will stay integral through the Branch-and-Cut tree; if so, strengthen
424  * coefficient */
425  if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
426  {
427  /* If cutelem < 0, then we know SCIPisZero(scip, cutelem) is true and hope it doesn't do much damage. */
428  cutelem = SCIPfrac(scip, rowelem);
429 
430  if( cutelem > f0 )
431  {
432  /* cut element if f > f0 */
433  cutelem = -((1.0 - cutelem) * ratiof0compl);
434  }
435  else
436  {
437  /* cut element if f <= f0 */
438  cutelem = -cutelem;
439  }
440  }
441  else
442  {
443  if( rowelem < 0.0 )
444  {
445  /* cut element if f < 0 */
446  cutelem = rowelem * ratiof0compl;
447  }
448  else
449  {
450  /* cut element if f >= 0 */
451  cutelem = -rowelem;
452  }
453  }
454 
455  if( ! SCIPisZero(scip, cutelem) )
456  {
457  /* Coefficient is large enough, we can keep it. */
458  SCIP_COL** rowcols;
459  SCIP_Real* rowvals;
460 
461  SCIP_Real act;
462  SCIP_Real rlhs;
463  SCIP_Real rrhs;
464  SCIP_Real rhsslack;
465 
466  /* get lhs/rhs */
467  rlhs = SCIProwGetLhs(row);
468  rrhs = SCIProwGetRhs(row);
469  assert( SCIPisLE(scip, rlhs, rrhs) );
470  assert( ! SCIPisInfinity(scip, rlhs) || ! SCIPisInfinity(scip, rrhs) );
471 
472  /* If the slack variable is fixed, we can ignore this cut coefficient. */
473  if( SCIPisFeasZero(scip, rrhs - rlhs) )
474  continue;
475 
476  act = SCIPgetRowLPActivity(scip, row);
477  rhsslack = rrhs - act;
478 
479  /* Unflip slack variable and adjust rhs if necessary. */
481  {
482  /* If >= or ranged constraint, flip element back to original */
483  assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
484  cutelem = -cutelem;
485  }
486 
487  rowcols = SCIProwGetCols(row);
488  rowvals = SCIProwGetVals(row);
489 
490  /* Eliminate slack variable. */
491  for( i = 0; i < SCIProwGetNLPNonz(row); ++i )
492  workcoefs[SCIPcolGetLPPos(rowcols[i])] -= cutelem * rowvals[i];
493 
494  if ( SCIPisFeasZero(scip, rhsslack) )
495  *cutrhs -= cutelem * (rrhs - SCIProwGetConstant(row));
496  else
497  {
498  assert( SCIPisFeasZero(scip, act - rlhs) );
499  *cutrhs -= cutelem * (rlhs - SCIProwGetConstant(row));
500  }
501  }
502  } /* for( c = 0; c < nrows; ++c) */
503 
504  /* Initialize cut activity. */
505  *cutact = 0.0;
506 
507  /* Modify cut to make it numerically safer, and check that it is numerically safe. */
508  success = modifyAndPackCut(scip, sepadata, ncols, cols, workcoefs, cutcoefs, cutind, cutnz, cutrhs);
509  if ( success )
510  {
511  success = checkNumerics(scip, sepadata, ncols, cols, cutcoefs, cutind, *cutnz, *cutrhs, cutact);
512  SCIPdebugMsg(scip, "checkNumerics returned: %u.\n", success);
513  return success;
514  }
515  SCIPdebugMsg(scip, "modifyAndPackCut was not successful.\n");
516 
517  return FALSE;
518 }
519 
520 
521 /*
522  * Callback methods
523  */
524 
525 /** copy method for separator plugins (called when SCIP copies plugins) */
526 static
527 SCIP_DECL_SEPACOPY(sepaCopyGMI)
528 { /*lint --e{715}*/
529  assert(scip != NULL);
530  assert(sepa != NULL);
531  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
532 
533  /* call inclusion method of constraint handler */
535 
536  return SCIP_OKAY;
537 }
538 
539 /** destructor of separator to free user data (called when SCIP is exiting) */
540 static
541 SCIP_DECL_SEPAFREE(sepaFreeGMI)
542 { /*lint --e{715}*/
543  SCIP_SEPADATA* sepadata;
544 
545  assert(scip != NULL);
546  assert(sepa != NULL);
547  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
548 
549  /* free separator data */
550  sepadata = SCIPsepaGetData(sepa);
551  assert(sepadata != NULL);
552 
553  SCIPfreeBlockMemory(scip, &sepadata);
554 
555  SCIPsepaSetData(sepa, NULL);
556 
557  return SCIP_OKAY;
558 }
559 
560 /** LP solution separation method of separator */
561 static
562 SCIP_DECL_SEPAEXECLP(sepaExeclpGMI)
563 { /*lint --e{715}*/
564  char cutname[SCIP_MAXSTRLEN];
565  SCIP_SEPADATA* sepadata;
566  SCIP_VAR** vars;
567  SCIP_COL** cols;
568  SCIP_ROW** rows;
569  SCIP_Real* binvrow;
570  SCIP_Real* binvarow;
571  SCIP_Real* cutcoefs;
572  SCIP_Real* workcoefs;
573  SCIP_Real cutrhs;
574  int* cutind;
575  int* basisind;
576  int nvars;
577  int ncols;
578  int nrows;
579  int ncalls;
580  int depth;
581  int maxsepacuts;
582  int ncuts;
583  int cutnz;
584  int c;
585  int i;
586  int j;
587 
588  assert(sepa != NULL);
589  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
590  assert(scip != NULL);
591  assert(result != NULL);
592 
593  *result = SCIP_DIDNOTRUN;
594 
595  /* Only call separator, if we are not close to terminating. */
596  if( SCIPisStopped(scip) )
597  return SCIP_OKAY;
598 
599  /* Only call separator, if an optimal LP solution is at hand. */
601  return SCIP_OKAY;
602 
603  /* Only call separator, if the LP solution is basic. */
604  if( ! SCIPisLPSolBasic(scip) )
605  return SCIP_OKAY;
606 
607  /* Only call separator, if there are fractional variables. */
608  if( SCIPgetNLPBranchCands(scip) == 0 )
609  return SCIP_OKAY;
610 
611  sepadata = SCIPsepaGetData(sepa);
612  assert(sepadata != NULL);
613 
614  depth = SCIPgetDepth(scip);
615  ncalls = SCIPsepaGetNCallsAtNode(sepa);
616 
617  /* Only call the GMI cut separator a given number of times at each node. */
618  if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
619  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
620  return SCIP_OKAY;
621 
622  /* get variables data */
623  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
624 
625  /* get LP data */
626  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
627  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
628 
629  /* exit if LP is trivial */
630  if( ncols == 0 || nrows == 0 )
631  return SCIP_OKAY;
632 
633  *result = SCIP_DIDNOTFIND;
634 
635  /* allocate temporary memory */
636  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
637  SCIP_CALL( SCIPallocBufferArray(scip, &workcoefs, ncols) );
638  SCIP_CALL( SCIPallocBufferArray(scip, &cutind, ncols) );
639  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
640  SCIP_CALL( SCIPallocBufferArray(scip, &binvarow, ncols) );
641  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
642 
643  /* get basis indices */
644  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
645 
646  /* get the maximal number of cuts allowed in a separation round */
647  if( depth == 0 )
648  maxsepacuts = sepadata->maxsepacutsroot;
649  else
650  maxsepacuts = sepadata->maxsepacuts;
651 
652  if( maxsepacuts == -1 )
653  maxsepacuts = INT_MAX;
654 
655  /* For all basic columns belonging to integer variables, try to generate a GMI cut. */
656  ncuts = 0;
657  for( i = 0; i < nrows && ncuts < maxsepacuts && ! SCIPisStopped(scip) && *result != SCIP_CUTOFF; ++i )
658  {
659  SCIP_Bool tryrow;
660  SCIP_Real primsol;
661 
662  tryrow = FALSE;
663  c = basisind[i];
664  primsol = SCIP_INVALID;
665 
666  SCIPdebugMsg(scip, "Row %d basic variable %d with value %f\n", i, basisind[i],
667  (c >= 0) ? SCIPcolGetPrimsol(cols[c]) : SCIPgetRowActivity(scip, rows[-c-1]));
668 
669  if( c >= 0 )
670  {
671  SCIP_VAR* var;
672  assert(c < ncols);
673  assert(cols[c] != NULL);
674  var = SCIPcolGetVar(cols[c]);
676  {
677  primsol = SCIPcolGetPrimsol(cols[c]);
678  assert(SCIPgetVarSol(scip, var) == primsol); /*lint !e777*/
679 
680  if( (SCIPfeasFrac(scip, primsol) >= sepadata->away) && (SCIPfeasFrac(scip, primsol) <= 1.0 - sepadata->away) )
681  {
682  SCIPdebugMsg(scip, "trying GMI cut for col <%s> [%g] row %i\n", SCIPvarGetName(var), primsol, i);
683  tryrow = TRUE;
684  }
685  }
686  }
687  else if( sepadata->separaterows )
688  {
689  SCIP_ROW* row;
690  assert(0 <= -c-1 && -c-1 < nrows);
691  row = rows[-c-1];
692  if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
693  {
694  /* Compute value of the slack variable (we only care about the correct fractionality) */
695  if ( SCIPisInfinity(scip, SCIProwGetRhs(row)) )
696  primsol = SCIProwGetLhs(row) - SCIPgetRowLPActivity(scip, row);
697  else
698  primsol = SCIProwGetRhs(row) - SCIPgetRowLPActivity(scip, row);
699 
700  if( (SCIPfeasFrac(scip, primsol) >= sepadata->away) && (SCIPfeasFrac(scip, primsol) <= 1.0 - sepadata->away) )
701  {
702  SCIPdebugMsg(scip, "trying GMI cut for row <%s> [%g]\n", SCIProwGetName(row), primsol);
704  tryrow = TRUE;
705  }
706  }
707  }
708 
709  if( tryrow )
710  {
711  SCIP_Real cutact;
712  SCIP_Bool success;
713  SCIP_Bool cutislocal;
714 
715  /* get the row of B^-1 for this basic integer variable with fractional solution value */
716  SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow, NULL, NULL) );
717 
718  /* get the tableau row for this basic integer variable with fractional solution value */
719  SCIP_CALL( SCIPgetLPBInvARow(scip, i, binvrow, binvarow, NULL, NULL) );
720 
721  /* this is an approximation (one could also pass over coefficients and check whether local rows have been used): */
722  cutislocal = (depth != 0) ? TRUE : FALSE;
723 
724  /* create a GMI cut out of the simplex tableau row */
725  success = getGMIFromRow(scip, sepadata, ncols, nrows, cols, rows, binvrow, binvarow, primsol, cutcoefs, cutind, &cutnz, &cutrhs, &cutact, workcoefs);
726 
727  SCIPdebugMsg(scip, " -> success = %u: %g <= %g\n", success, cutact, cutrhs);
728 
729  /* if successful, add the row as a cut */
730  if( success )
731  {
732  SCIP_ROW* cut;
733 
734  /* construct cut name */
735  if( c >= 0 )
736  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gmi%d_x%d", SCIPgetNLPs(scip), c);
737  else
738  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gmi%d_s%d", SCIPgetNLPs(scip), -c-1);
739 
740  /* create empty cut */
741  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
742 
743  /* cache the row extension and only flush them if the cut gets added */
745 
746  /* collect all non-zero coefficients */
747  for( j = 0; j < cutnz; ++j )
748  {
749  SCIP_CALL( SCIPaddVarToRow(scip, cut, SCIPcolGetVar(cols[cutind[j]]), cutcoefs[j]) );
750  }
751 
752  if( SCIProwGetNNonz(cut) == 0 )
753  {
754  assert(SCIPisFeasNegative(scip, cutrhs));
755  SCIPdebugMsg(scip, " -> GMI cut detected infeasibility with cut 0 <= %f.\n", cutrhs);
756  *result = SCIP_CUTOFF;
757  break;
758  }
759 
760  /* Only take efficacious cuts, except for cuts with one non-zero coefficient (= bound
761  * changes); the latter cuts will be handeled internally in sepastore. */
762  if( SCIProwGetNNonz(cut) == 1 || SCIPisCutEfficacious(scip, NULL, cut) )
763  {
764  SCIP_Bool infeasible;
765 
766  SCIPdebugMsg(scip, " -> found GMI cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f).\n",
767  cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
771 
772  /* flush all changes before adding the cut */
774 
775  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, &infeasible) );
776 
777  /* add global cuts that are not implicit bound changes to the cut pool */
778  if( ! cutislocal && SCIProwGetNNonz(cut) > 1 )
779  {
780  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
781  }
782 
783  if ( infeasible )
784  *result = SCIP_CUTOFF;
785  else
786  *result = SCIP_SEPARATED;
787  ncuts++;
788  }
789 
790  /* release the row */
791  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
792  }
793  }
794  }
795 
796  /* free temporary memory */
797  SCIPfreeBufferArray(scip, &binvarow);
798  SCIPfreeBufferArray(scip, &binvrow);
799  SCIPfreeBufferArray(scip, &basisind);
800  SCIPfreeBufferArray(scip, &workcoefs);
801  SCIPfreeBufferArray(scip, &cutcoefs);
802  SCIPfreeBufferArray(scip, &cutind);
803 
804  SCIPdebugMsg(scip, "end searching GMI cuts: found %d cuts.\n", ncuts);
805 
806  sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
807 
808  return SCIP_OKAY;
809 }
810 
811 
812 /*
813  * separator specific interface methods
814  */
815 
816 /** creates the GMI MIR cut separator and includes it in SCIP */
818  SCIP* scip /**< SCIP data structure */
819  )
820 {
821  SCIP_SEPADATA* sepadata;
822  SCIP_SEPA* sepa;
823 
824  /* create separator data */
825  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
826  sepadata->lastncutsfound = 0;
827 
828  /* include separator */
830  SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpGMI, NULL, sepadata) );
831 
832  assert(sepa != NULL);
833 
834  /* set non-NULL pointers to callback methods */
835  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyGMI) );
836  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeGMI) );
837 
838  /* add separator parameters */
840  "separating/gmi/maxrounds",
841  "maximal number of GMI separation rounds per node (-1: unlimited)",
842  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
844  "separating/gmi/maxroundsroot",
845  "maximal number of GMI separation rounds in the root node (-1: unlimited)",
846  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
848  "separating/gmi/maxsepacuts",
849  "maximal number of GMI cuts separated per separation round (-1: unlimited)",
850  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, -1, INT_MAX, NULL, NULL) );
852  "separating/gmi/maxsepacutsroot",
853  "maximal number of GMI cuts separated per separation round in the root node (-1: unlimited)",
854  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, -1, INT_MAX, NULL, NULL) );
856  "separating/gmi/dynamiccuts",
857  "should generated cuts be removed from the LP if they are no longer tight?",
858  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
860  "separating/gmi/separaterows",
861  "separate rows with integral slack",
862  &sepadata->separaterows, FALSE, DEFAULT_SEPARATEROWS, NULL, NULL) );
864  "separating/gmi/away",
865  "minimal fractionality of a basic variable in order to try GMI cut",
866  &sepadata->away, FALSE, DEFAULT_AWAY, 0.0, 0.5, NULL, NULL) );
868  "separating/gmi/minviolation",
869  "minimal violation to accept cut",
870  &sepadata->minviolation, FALSE, DEFAULT_MIN_VIOLATION, 0.0, 1.0, NULL, NULL) );
872  "separating/gmi/epscoeff",
873  "tolerance for zeroing out small coefficients",
874  &sepadata->epscoeff, FALSE, DEFAULT_EPS_COEFF, 0.0, 0.01, NULL, NULL) );
876  "separating/gmi/epsrelaxabs",
877  "absolute cut rhs relaxation",
878  &sepadata->epsrelaxabs, FALSE, DEFAULT_EPS_RELAX_ABS, 0.0, SCIP_REAL_MAX, NULL, NULL) );
880  "separating/gmi/epsrelaxrel",
881  "relative cut rhs relaxation",
882  &sepadata->epsrelaxrel, FALSE, DEFAULT_EPS_RELAX_REL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
884  "separating/gmi/maxdynamism",
885  "maximal valid range max(|weights|)/min(|weights|) of cut coefficients",
886  &sepadata->maxdynamism, FALSE, DEFAULT_MAX_DYN, 0.0, SCIP_REAL_MAX, NULL, NULL) );
888  "separating/gmi/maxsuppabs",
889  "maximum cut support - absolute value in the formula",
890  &sepadata->maxsuppabs, FALSE, DEFAULT_MAX_SUPP_ABS, 0, INT_MAX, NULL, NULL) );
892  "separating/gmi/maxsupprel",
893  "maximum cut support - relative value in the formula",
894  &sepadata->maxsupprel, FALSE, DEFAULT_MAX_SUPP_REL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
895 
896  return SCIP_OKAY;
897 }
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:462
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:17076
#define SCIP_MAXSTRLEN
Definition: def.h:273
static SCIP_DECL_SEPACOPY(sepaCopyGMI)
Definition: sepa_gmi.c:527
#define DEFAULT_AWAY
Definition: sepa_gmi.c:85
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:16921
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17062
#define DEFAULT_SEPARATEROWS
Definition: sepa_gmi.c:83
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2152
static SCIP_DECL_SEPAFREE(sepaFreeGMI)
Definition: sepa_gmi.c:541
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:419
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17107
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17177
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:72
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:142
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1604
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17350
#define DEFAULT_MIN_VIOLATION
Definition: sepa_gmi.c:86
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define DEFAULT_MAX_DYN
Definition: sepa_gmi.c:90
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17260
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:16822
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:65
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:17117
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1844
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_gmi.c:81
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1581
static SCIP_Bool modifyAndPackCut(SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, SCIP_COL **cols, SCIP_Real *densecoefs, SCIP_Real *sparsecoefs, int *cutind, int *cutnz, SCIP_Real *cutrhs)
Definition: sepa_gmi.c:126
#define DEFAULT_EPS_COEFF
Definition: sepa_gmi.c:87
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17087
#define DEFAULT_MAX_SUPP_REL
Definition: sepa_gmi.c:92
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:540
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1508
#define SEPA_NAME
Definition: sepa_gmi.c:70
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17097
static SCIP_DECL_SEPAEXECLP(sepaExeclpGMI)
Definition: sepa_gmi.c:562
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:187
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16855
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:16832
SCIP_EXPORT SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:608
SCIP_RETCODE SCIPincludeSepaGMI(SCIP *scip)
Definition: sepa_gmi.c:817
SCIP_EXPORT const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:697
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:637
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:17189
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
SCIP_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:755
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_gmi.c:79
#define SCIP_Bool
Definition: def.h:70
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:17240
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:100
static SCIP_Bool getGMIFromRow(SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, int nrows, SCIP_COL **cols, SCIP_ROW **rows, SCIP_Real *binvrow, SCIP_Real *binvarow, SCIP_Real rowrhs, SCIP_Real *cutcoefs, int *cutind, int *cutnz, SCIP_Real *cutrhs, SCIP_Real *cutact, SCIP_Real *workcoefs)
Definition: sepa_gmi.c:267
Gomory Mixed-Integer Cuts.
#define DEFAULT_DYNAMICCUTS
Definition: sepa_gmi.c:82
#define SEPA_USESSUBSCIP
Definition: sepa_gmi.c:75
#define MAX(x, y)
Definition: tclique_def.h:83
#define DEFAULT_MAX_SUPP_ABS
Definition: sepa_gmi.c:91
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17141
#define DEFAULT_MAXROUNDS
Definition: sepa_gmi.c:78
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:88
#define SEPA_DELAY
Definition: sepa_gmi.c:76
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16901
int SCIPgetNCutsFound(SCIP *scip)
#define SEPA_FREQ
Definition: sepa_gmi.c:73
#define SCIP_REAL_MAX
Definition: def.h:164
#define SEPA_PRIORITY
Definition: sepa_gmi.c:72
static SCIP_Bool checkNumerics(SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, SCIP_COL **cols, SCIP_Real *cutcoefs, int *cutind, int cutnz, SCIP_Real cutrhs, SCIP_Real *cutact)
Definition: sepa_gmi.c:203
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:221
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1933
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1641
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1860
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10590
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:2311
#define SCIP_Real
Definition: def.h:163
#define SEPA_DESC
Definition: sepa_gmi.c:71
#define DEFAULT_EPS_RELAX_ABS
Definition: sepa_gmi.c:88
#define SEPA_MAXBOUNDDIST
Definition: sepa_gmi.c:74
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17200
#define SCIP_INVALID
Definition: def.h:183
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip_lp.c:656
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:684
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:16890
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:332
SCIP_EXPORT void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:618
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17151
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1862
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:158
SCIP_EXPORT int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:824
#define DEFAULT_MAXSEPACUTS
Definition: sepa_gmi.c:80
#define EPSZ(x, eps)
Definition: def.h:193
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:43
#define DEFAULT_EPS_RELAX_REL
Definition: sepa_gmi.c:89
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16942
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1399
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2044