# 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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
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 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 Gomory separation rounds per node (-1: unlimited) */
79 #define DEFAULT_MAXROUNDSROOT 30 /**< maximal number of Gomory separation rounds in the root node (-1: unlimited) */
80 #define DEFAULT_MAXSEPACUTS -1 /**< maximal number of Gomory cuts separated per separation round */
81 #define DEFAULT_MAXSEPACUTSROOT -1 /**< maximal number of Gomory 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 */
97 {
98  int maxrounds; /**< maximal number of Gomory separation rounds per node (-1: unlimited) */
99  int maxroundsroot; /**< maximal number of Gomory separation rounds in the root node (-1: unlimited) */
100  int maxsepacuts; /**< maximal number of Gomory cuts separated per separation round */
101  int maxsepacutsroot; /**< maximal number of Gomory 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, 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 */
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 */
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, 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 */
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 */
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 */
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}*/
544
545  assert(scip != NULL);
546  assert(sepa != NULL);
547  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
548
549  /* free separator data */
552
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];
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
613
614  depth = SCIPgetDepth(scip);
615  ncalls = SCIPsepaGetNCallsAtNode(sepa);
616
617  /* Only call the Gomory cut separator a given number of times at each node. */
618  if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot) || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
619  return SCIP_OKAY;
620
621  /* get variables data */
622  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
623
624  /* get LP data */
625  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
626  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
627
628  /* exit if LP is trivial */
629  if( ncols == 0 || nrows == 0 )
630  return SCIP_OKAY;
631
632  *result = SCIP_DIDNOTFIND;
633
634  /* allocate temporary memory */
635  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
636  SCIP_CALL( SCIPallocBufferArray(scip, &workcoefs, ncols) );
637  SCIP_CALL( SCIPallocBufferArray(scip, &cutind, ncols) );
638  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
639  SCIP_CALL( SCIPallocBufferArray(scip, &binvarow, ncols) );
640  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
641
642  /* get basis indices */
643  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
644
645  /* get the maximal number of cuts allowed in a separation round */
646  if( depth == 0 )
648  else
650
651  if( maxsepacuts == -1 )
652  maxsepacuts = INT_MAX;
653
654  /* For all basic columns belonging to integer variables, try to generate a Gomory cut. */
655  ncuts = 0;
656  for( i = 0; i < nrows && ncuts < maxsepacuts && ! SCIPisStopped(scip) && *result != SCIP_CUTOFF; ++i )
657  {
658  SCIP_Bool tryrow;
659  SCIP_Real primsol;
660
661  tryrow = FALSE;
662  c = basisind[i];
663  primsol = SCIP_INVALID;
664
665  SCIPdebugMsg(scip, "Row %d basic variable %d with value %f\n", i, basisind[i], (c >= 0) ? SCIPcolGetPrimsol(cols[c]) : SCIPgetRowActivity(scip, rows[-c-1]));
666  if( c >= 0 )
667  {
668  SCIP_VAR* var;
669  assert(c < ncols);
670  assert(cols[c] != NULL);
671  var = SCIPcolGetVar(cols[c]);
673  {
674  primsol = SCIPcolGetPrimsol(cols[c]);
675  assert(SCIPgetVarSol(scip, var) == primsol); /*lint !e777*/
676
677  if( (SCIPfeasFrac(scip, primsol) >= sepadata->away) && (SCIPfeasFrac(scip, primsol) <= 1.0 - sepadata->away) )
678  {
679  SCIPdebugMsg(scip, "trying Gomory cut for col <%s> [%g] row %i\n", SCIPvarGetName(var), primsol, i);
680  tryrow = TRUE;
681  }
682  }
683  }
685  {
686  SCIP_ROW* row;
687  assert(0 <= -c-1 && -c-1 < nrows);
688  row = rows[-c-1];
689  if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
690  {
691  /* Compute value of the slack variable (we only care about the correct fractionality) */
692  if ( SCIPisInfinity(scip, SCIProwGetRhs(row)) )
693  primsol = SCIProwGetLhs(row) - SCIPgetRowLPActivity(scip, row);
694  else
695  primsol = SCIProwGetRhs(row) - SCIPgetRowLPActivity(scip, row);
696
697  if( (SCIPfeasFrac(scip, primsol) >= sepadata->away) && (SCIPfeasFrac(scip, primsol) <= 1.0 - sepadata->away) )
698  {
699  SCIPdebugMsg(scip, "trying Gomory cut for row <%s> [%g]\n", SCIProwGetName(row), primsol);
701  tryrow = TRUE;
702  }
703  }
704  }
705
706  if( tryrow )
707  {
708  SCIP_Real cutact;
709  SCIP_Bool success;
710  SCIP_Bool cutislocal;
711
712  /* get the row of B^-1 for this basic integer variable with fractional solution value */
713  SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow, NULL, NULL) );
714
715  /* get the tableau row for this basic integer variable with fractional solution value */
716  SCIP_CALL( SCIPgetLPBInvARow(scip, i, binvrow, binvarow, NULL, NULL) );
717
718  /* this is an approximation (one could also pass over coefficients and check whether local rows have been used): */
719  cutislocal = (depth != 0) ? TRUE : FALSE;
720
721  /* create a GMI cut out of the simplex tableau row */
722  success = getGMIFromRow(scip, sepadata, ncols, nrows, cols, rows, binvrow, binvarow, primsol, cutcoefs, cutind, &cutnz, &cutrhs, &cutact, workcoefs);
723
724  SCIPdebugMsg(scip, " -> success = %u: %g <= %g\n", success, cutact, cutrhs);
725
726  /* if successful, add the row as a cut */
727  if( success )
728  {
729  SCIP_ROW* cut;
730
731  /* construct cut name */
732  if( c >= 0 )
733  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gmi%d_x%d", SCIPgetNLPs(scip), c);
734  else
735  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gmi%d_s%d", SCIPgetNLPs(scip), -c-1);
736
737  /* create empty cut */
738  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
739
740  /* cache the row extension and only flush them if the cut gets added */
742
743  /* collect all non-zero coefficients */
744  for( j = 0; j < cutnz; ++j )
745  {
746  SCIP_CALL( SCIPaddVarToRow(scip, cut, SCIPcolGetVar(cols[cutind[j]]), cutcoefs[j]) );
747  }
748
749  if( SCIProwGetNNonz(cut) == 0 )
750  {
751  assert(SCIPisFeasNegative(scip, cutrhs));
752  SCIPdebugMsg(scip, " -> Gomory cut detected infeasibility with cut 0 <= %f\n", cutrhs);
753  *result = SCIP_CUTOFF;
754  break;
755  }
756
757  /* Only take efficacious cuts, except for cuts with one non-zero coefficient (= bound
758  changes); the latter cuts will be handeled internally in sepastore. */
759  if( SCIProwGetNNonz(cut) == 1 || SCIPisCutEfficacious(scip, NULL, cut) )
760  {
761  SCIP_Bool infeasible;
762
763  SCIPdebugMsg(scip, " -> Gomory cut for <%s>: act=%f, rhs=%f, eff=%f\n",
764  c >= 0 ? SCIPvarGetName(SCIPcolGetVar(cols[c])) : SCIProwGetName(rows[-c-1]),
765  cutact, cutrhs, SCIPgetCutEfficacy(scip, NULL, cut));
766
767  SCIPdebugMsg(scip, " -> found Gomory cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
768  cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
772
773  /* flush all changes before adding the cut */
775
776  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, &infeasible) );
777
778  /* add global cuts that are not implicit bound changes to the cut pool */
779  if( ! cutislocal && SCIProwGetNNonz(cut) > 1 )
780  {
782  }
783
784  if ( infeasible )
785  *result = SCIP_CUTOFF;
786  else
787  *result = SCIP_SEPARATED;
788  ncuts++;
789  }
790
791  /* release the row */
792  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
793  }
794  }
795  }
796
797  /* free temporary memory */
798  SCIPfreeBufferArray(scip, &binvarow);
799  SCIPfreeBufferArray(scip, &binvrow);
800  SCIPfreeBufferArray(scip, &basisind);
801  SCIPfreeBufferArray(scip, &workcoefs);
802  SCIPfreeBufferArray(scip, &cutcoefs);
803  SCIPfreeBufferArray(scip, &cutind);
804
805  SCIPdebugMsg(scip, "end searching Gomory cuts: found %d cuts.\n", ncuts);
806
808
809  return SCIP_OKAY;
810 }
811
812
813 /*
814  * separator specific interface methods
815  */
816
817 /** creates the GMI MIR cut separator and includes it in SCIP */
819  SCIP* scip /**< SCIP data structure */
820  )
821 {
823  SCIP_SEPA* sepa;
824
825  /* create separator data */
828
829  /* include separator */
831  SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpGMI, NULL, sepadata) );
832
833  assert(sepa != NULL);
834
835  /* set non-NULL pointers to callback methods */
836  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyGMI) );
837  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeGMI) );
838
839  /* add separator parameters */
841  "separating/gmi/maxrounds",
842  "maximal number of gmi separation rounds per node (-1: unlimited)",
843  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
845  "separating/gmi/maxroundsroot",
846  "maximal number of gmi separation rounds in the root node (-1: unlimited)",
847  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
849  "separating/gmi/maxsepacuts",
850  "maximal number of gmi cuts separated per separation round (-1: unlimited)",
851  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, -1, INT_MAX, NULL, NULL) );
853  "separating/gmi/maxsepacutsroot",
854  "maximal number of gmi cuts separated per separation round in the root node (-1: unlimited)",
855  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, -1, INT_MAX, NULL, NULL) );
857  "separating/gmi/dynamiccuts",
858  "should generated cuts be removed from the LP if they are no longer tight?",
859  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
861  "separating/gmi/separaterows",
862  "separate rows with integral slack",
863  &sepadata->separaterows, FALSE, DEFAULT_SEPARATEROWS, NULL, NULL) );
865  "separating/gmi/away",
866  "minimal fractionality of a basic variable in order to try GMI cut",
867  &sepadata->away, FALSE, DEFAULT_AWAY, 0.0, 0.5, NULL, NULL) );
869  "separating/gmi/minviolation",
870  "minimal violation to accept cut",
871  &sepadata->minviolation, FALSE, DEFAULT_MIN_VIOLATION, 0.0, 1.0, NULL, NULL) );
873  "separating/gmi/epscoeff",
874  "tolerance for zeroing out small coefficients",
875  &sepadata->epscoeff, FALSE, DEFAULT_EPS_COEFF, 0.0, 0.01, NULL, NULL) );
877  "separating/gmi/epsrelaxabs",
878  "absolute cut rhs relaxation",
879  &sepadata->epsrelaxabs, FALSE, DEFAULT_EPS_RELAX_ABS, 0.0, SCIP_REAL_MAX, NULL, NULL) );
881  "separating/gmi/epsrelaxrel",
882  "relative cut rhs relaxation",
883  &sepadata->epsrelaxrel, FALSE, DEFAULT_EPS_RELAX_REL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
885  "separating/gmi/maxdynamism",
886  "maximal valid range max(|weights|)/min(|weights|) of cut coefficients",
887  &sepadata->maxdynamism, FALSE, DEFAULT_MAX_DYN, 0.0, SCIP_REAL_MAX, NULL, NULL) );
889  "separating/gmi/maxsuppabs",
890  "maximum cut support - absolute value in the formula",
891  &sepadata->maxsuppabs, FALSE, DEFAULT_MAX_SUPP_ABS, 0, INT_MAX, NULL, NULL) );
893  "separating/gmi/maxsupprel",
894  "maximum cut support - relative value in the formula",
895  &sepadata->maxsupprel, FALSE, DEFAULT_MAX_SUPP_REL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
896
897  return SCIP_OKAY;
898 }
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:717
#define NULL
Definition: def.h:246
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1547
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1570
#define SCIP_MAXSTRLEN
Definition: def.h:267
static SCIP_DECL_SEPACOPY(sepaCopyGMI)
Definition: sepa_gmi.c:527
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:16718
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1607
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16880
#define DEFAULT_AWAY
Definition: sepa_gmi.c:85
#define DEFAULT_SEPARATEROWS
Definition: sepa_gmi.c:83
static SCIP_DECL_SEPAFREE(sepaFreeGMI)
Definition: sepa_gmi.c:541
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17018
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:16894
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1918
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16959
#define FALSE
Definition: def.h:72
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:16749
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:16660
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:17007
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10253
#define TRUE
Definition: def.h:71
#define SCIPdebug(x)
Definition: pub_message.h:74
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:689
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
#define DEFAULT_MIN_VIOLATION
Definition: sepa_gmi.c:86
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:495
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:417
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:220
#define DEFAULT_MAX_DYN
Definition: sepa_gmi.c:90
#define SCIPdebugMsg
Definition: scip_message.h:88
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:155
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1828
Definition: sepa.c:600
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_gmi.c:81
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:670
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:161
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_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16683
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1810
#define DEFAULT_MAX_SUPP_REL
Definition: sepa_gmi.c:92
int SCIPgetNCutsFound(SCIP *scip)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:816
#define SEPA_NAME
Definition: sepa_gmi.c:70
static SCIP_DECL_SEPAEXECLP(sepaExeclpGMI)
Definition: sepa_gmi.c:562
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:16650
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16730
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:17058
Definition: sepa.c:610
#define REALABS(x)
Definition: def.h:181
#define SCIP_CALL(x)
Definition: def.h:358
SCIP_RETCODE SCIPincludeSepaGMI(SCIP *scip)
Definition: sepa_gmi.c:818
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16969
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1899
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:294
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17078
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16905
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:178
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
SCIP_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:788
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16915
public data structures and miscellaneous methods
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_gmi.c:79
#define SCIP_Bool
Definition: def.h:69
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:226
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
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:715
#define SEPA_USESSUBSCIP
Definition: sepa_gmi.c:75
#define DEFAULT_MAX_SUPP_ABS
Definition: sepa_gmi.c:91
Definition: scip_cut.c:405
#define MIN(x, y)
Definition: def.h:216
#define DEFAULT_MAXROUNDS
Definition: sepa_gmi.c:78
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:1365
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:138
#define SEPA_DELAY
Definition: sepa_gmi.c:76
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip_lp.c:689
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define SEPA_FREQ
Definition: sepa_gmi.c:73
#define SCIP_REAL_MAX
Definition: def.h:158
#define SEPA_PRIORITY
Definition: sepa_gmi.c:72
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16925
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1474
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
#define MAX(x, y)
Definition: def.h:215
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:236
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16729
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17148
#define SCIP_Real
Definition: def.h:157
#define SEPA_DESC
Definition: sepa_gmi.c:71
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:738
#define DEFAULT_EPS_RELAX_ABS
Definition: sepa_gmi.c:88
#define SEPA_MAXBOUNDDIST
Definition: sepa_gmi.c:74
#define SCIP_INVALID
Definition: def.h:177
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2099
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16895
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:2309
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:119
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:573
SCIP_Longint SCIPgetNLPs(SCIP *scip)
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16770
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:16935
#define DEFAULT_MAXSEPACUTS
Definition: sepa_gmi.c:80
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:211
#define EPSZ(x, eps)
Definition: def.h:187