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-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* 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 AWAY 0.005 /**< minimal fractionality of a basic variable in order to try GMI cut - default */
86 #define MIN_VIOLATION 0.00 /**< minimal violation to accept cut - default */
87 #define EPS_COEFF 1e-11 /**< tolerance for zeroing out small coefficients - default */
88 #define EPS_RELAX_ABS 1e-11 /**< absolute cut rhs relaxation - default */
89 #define EPS_RELAX_REL 1e-13 /**< relative cut rhs relaxation - default */
90 #define MAX_DYN 1.0e+6 /**< maximal valid range max(|weights|)/min(|weights|) of cut coefficients - default */
91 #define MAX_SUPP_ABS 1000 /**< maximum cut support - absolute value in the formula - default */
92 #define 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 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
126 SCIP_Bool modifyAndPackCut(
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, /**< number of nonzero elements in the cut in sparse format on output */
135  SCIP_Real* cutrhs /**< rhs of the cut */
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, Nannicini for more information. Returns
200  * TRUE if cut is accepted, FALSE if it is discarded.
201  */
202 static
203 SCIP_Bool checkNumerics(
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 /**< 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(cutnz != NULL);
225  assert(cutrhs != NULL);
226  assert(cutact != NULL);
227  assert(*cutnz > 0);
228 
229  /* Check maximum support */
230  if( *cutnz > (ncols)*(sepadata->maxsupprel) + sepadata->maxsuppabs )
231  {
232  SCIPdebugMsg(scip, "Cut too dense (%d > %d).\n", *cutnz, (int) ((ncols)*(sepadata->maxsupprel) + sepadata->maxsuppabs));
233  return FALSE;
234  }
235 
236  /* Compute cut violation and dynamism */
237  mincoef = SCIP_REAL_MAX;
238  maxcoef = 0.0;
239  *cutact = 0.0;
240 
241  for( i = 0; i < *cutnz; ++i )
242  {
243  mincoef = MIN(mincoef, REALABS(cutcoefs[i])); /*lint !e666*/
244  maxcoef = MAX(maxcoef, REALABS(cutcoefs[i])); /*lint !e666*/
245  *cutact += cutcoefs[i] * SCIPcolGetPrimsol(cols[cutind[i]]);
246  }
247 
248  /* Check dynamism */
249  if( maxcoef > mincoef * sepadata->maxdynamism )
250  {
251  SCIPdebugMsg(scip, "Cut too dynamic (%g > %g).\n", maxcoef, mincoef * sepadata->maxdynamism);
252  return FALSE;
253  }
254 
255  /* Check minimum violation */
256  violation = *cutact - *cutrhs;
257  if( REALABS(*cutrhs) > 1.0 )
258  violation /= REALABS(*cutrhs);
259 
260  return (violation >= sepadata->minviolation) ? TRUE : FALSE;
261 }
262 
263 /** Method to obtain a GMI in the space of the original variables from a row of the simplex tableau.
264  *
265  * Returns TRUE if cut is successfully created, FALSE if no cut was generated or if it should be discarded. If the
266  * function returns FALSE, the contents of cutcoefs, cutind, cutnz, cutrhs, cutact may be garbage.
267  */
268 static
269 SCIP_Bool getGMIFromRow(
270  SCIP* scip, /**< pointer to the SCIP environment */
271  SCIP_SEPADATA* sepadata, /**< pointer to separator data */
272  int ncols, /**< number of columns in the LP */
273  int nrows, /**< number of rows in the LP */
274  SCIP_COL** cols, /**< columns of the LP */
275  SCIP_ROW** rows, /**< rows of the LP */
276  SCIP_Real* binvrow, /**< row of the basis inverse */
277  SCIP_Real* binvarow, /**< row of the simplex tableau */
278  SCIP_Real rowrhs, /**< rhs of the tableau row, i.e. corresponding element in the LP solution */
279  SCIP_Real* cutcoefs, /**< cut elements in sparse format will go here - must be of size ncols */
280  int* cutind, /**< indices of nonzero cut coefficients will go here - must be of size ncols */
281  int* cutnz, /**< number of nonzero elements in the cuts will go here */
282  SCIP_Real* cutrhs, /**< cut rhs will go here */
283  SCIP_Real* cutact, /**< cut activity at the current LP optimum will go here - only meaningful if returns TRUE */
284  SCIP_Real* workcoefs /**< working array of size ncols, allocated by caller for efficiency */
285  )
286 {
287  SCIP_COL* col;
288  SCIP_ROW* row;
289  SCIP_Real rowelem;
290  SCIP_Real cutelem;
291  SCIP_Real f0;
292  SCIP_Real ratiof0compl;
293  SCIP_Bool success;
294  int i;
295  int c;
296 
297  assert(scip != NULL);
298  assert(cols != NULL);
299  assert(rows != NULL);
300  assert(binvrow != NULL);
301  assert(binvarow != NULL);
302  assert(cutcoefs != NULL);
303  assert(cutind != NULL);
304  assert(cutnz != NULL);
305  assert(cutrhs != NULL);
306  assert(cutact != NULL);
307  assert(workcoefs != NULL);
308 
309  /* Compute cut fractionality f0 and f0/(1-f0). */
310  f0 = SCIPfeasFrac(scip, rowrhs);
311  ratiof0compl = f0/(1-f0);
312 
313  /* rhs of the cut is the fractional part of the LP solution for the basic variable */
314  *cutrhs = -f0;
315 
316  /* clear cutcoefs */
317  BMSclearMemoryArray(workcoefs, ncols);
318 
319  /* Generate cut coefficients for the original variables. We first use workcoefs to store the cut in dense form, then
320  we clean and pack the cut to sparse form in cutcoefs. */
321  for( c = 0; c < ncols; ++ c)
322  {
323  col = cols[c];
324  assert( col != NULL );
325 
326  /* Get simplex tableau element */
327  switch ( SCIPcolGetBasisStatus(col) )
328  {
329  case SCIP_BASESTAT_LOWER:
330  /* Take element if nonbasic at lower bound */
331  rowelem = binvarow[c];
332  break;
333  case SCIP_BASESTAT_UPPER:
334  /* Flip element if nonbasic at upper bound */
335  rowelem = -binvarow[c];
336  break;
337  case SCIP_BASESTAT_ZERO:
338  /* Nonbasic free variable at zero: cut coefficient is zero, skip */
339  continue;
340  case SCIP_BASESTAT_BASIC:
341  default:
342  /* Basic variable: skip */
343  continue;
344  }
345 
346  /* Integer variables */
347  if( SCIPcolIsIntegral(col) )
348  {
349  /* if cutelem < 0, then we know SCIPisZero(scip, cutelem) is true and hope it doesn't do much damage */
350  cutelem = SCIPfrac(scip, rowelem);
351 
352  if( cutelem > f0 )
353  {
354  /* cut element if f > f0 */
355  cutelem = -((1.0 - cutelem) * ratiof0compl);
356  }
357  else
358  {
359  /* cut element if f <= f0 */
360  cutelem = -cutelem;
361  }
362  }
363  /* Continuous variables */
364  else
365  {
366  if( rowelem < 0.0 )
367  {
368  /* cut element if f < 0 */
369  cutelem = rowelem * ratiof0compl;
370  }
371  else
372  {
373  /* cut element if f >= 0 */
374  cutelem = -rowelem;
375  }
376  }
377 
378  if( ! SCIPisZero(scip, cutelem) )
379  {
380  /* Unflip if necessary, and adjust rhs if at lower or upper bound. */
381  if( SCIPcolGetBasisStatus(col) == SCIP_BASESTAT_UPPER )
382  {
383  cutelem = -cutelem;
384  *cutrhs += cutelem * SCIPcolGetUb(col);
385  }
386  else
387  *cutrhs += cutelem * SCIPcolGetLb(col);
388 
389  /* Add coefficient to cut in dense form. */
390  workcoefs[SCIPcolGetLPPos(col)] = cutelem;
391  }
392  } /* for( c = 0; c < ncols; ++c) */
393 
394  /* Generate cut coefficients for the slack variables. */
395  for( c = 0; c < nrows; ++c )
396  {
397  row = rows[c];
398  assert( row != NULL );
399 
400  /* Get simplex tableau element. */
401  switch ( SCIProwGetBasisStatus(row) )
402  {
403  case SCIP_BASESTAT_LOWER:
404  /* Take element if nonbasic at lower bound. */
405  rowelem = binvrow[SCIProwGetLPPos(row)];
406  /* But if this is a >= or ranged constraint at the lower bound, we have to flip the row element. */
407  if( !SCIPisInfinity(scip, -SCIProwGetLhs(row)) )
408  rowelem = -rowelem;
409  break;
410  case SCIP_BASESTAT_UPPER:
411  /* Take element if nonbasic at upper bound - see notes at beginning of file: only nonpositive slack variables
412  can be nonbasic at upper, therefore they should be flipped twice and we can take the element directly. */
413  rowelem = binvrow[SCIProwGetLPPos(row)];
414  break;
415  case SCIP_BASESTAT_ZERO:
416  /* Nonbasic free variable at zero: cut coefficient is zero, skip */
417  SCIPdebugMsg(scip, "Free nonbasic slack variable, this should not happen!\n");
418  continue;
419  case SCIP_BASESTAT_BASIC:
420  default:
421  /* Basic variable: skip */
422  continue;
423  }
424 
425  /* Check if row is integral and will stay integral through the Branch-and-Cut tree; if so, strengthen
426  * coefficient */
427  if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
428  {
429  /* if cutelem < 0, then we know SCIPisZero(scip, cutelem) is true and hope it doesn't do much damage */
430  cutelem = SCIPfrac(scip, rowelem);
431 
432  if( cutelem > f0 )
433  {
434  /* cut element if f > f0 */
435  cutelem = -((1.0 - cutelem) * ratiof0compl);
436  }
437  else
438  {
439  /* cut element if f <= f0 */
440  cutelem = -cutelem;
441  }
442  }
443  else
444  {
445  if( rowelem < 0.0 )
446  {
447  /* cut element if f < 0 */
448  cutelem = rowelem * ratiof0compl;
449  }
450  else
451  {
452  /* cut element if f >= 0 */
453  cutelem = -rowelem;
454  }
455  }
456 
457  if( ! SCIPisZero(scip, cutelem) )
458  {
459  /* Coefficient is large enough, we can keep it. */
460  SCIP_COL** rowcols;
461  SCIP_Real* rowvals;
462 
463  SCIP_Real act;
464  SCIP_Real rlhs;
465  SCIP_Real rrhs;
466  SCIP_Real rhsslack;
467 
468  /* get lhs/rhs */
469  rlhs = SCIProwGetLhs(row);
470  rrhs = SCIProwGetRhs(row);
471  assert( SCIPisLE(scip, rlhs, rrhs) );
472  assert( ! SCIPisInfinity(scip, rlhs) || ! SCIPisInfinity(scip, rrhs) );
473 
474  /* If the slack variable is fixed, we can ignore this cut coefficient */
475  if( SCIPisFeasZero(scip, rrhs - rlhs) )
476  continue;
477 
478  act = SCIPgetRowLPActivity(scip, row);
479  rhsslack = rrhs - act;
480 
481  /* Unflip slack variable and adjust rhs if necessary. */
482  if( SCIProwGetBasisStatus(row) == SCIP_BASESTAT_LOWER )
483  {
484  /* If >= or ranged constraint, flip element back to original */
485  assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
486  cutelem = -cutelem;
487  }
488 
489  rowcols = SCIProwGetCols(row);
490  rowvals = SCIProwGetVals(row);
491 
492  /* Eliminate slack variable. */
493  for( i = 0; i < SCIProwGetNLPNonz(row); ++i )
494  workcoefs[SCIPcolGetLPPos(rowcols[i])] -= cutelem * rowvals[i];
495 
496  if ( SCIPisFeasZero(scip, rhsslack) )
497  *cutrhs -= cutelem * (rrhs - SCIProwGetConstant(row));
498  else
499  {
500  assert( SCIPisFeasZero(scip, act - rlhs) );
501  *cutrhs -= cutelem * (rlhs - SCIProwGetConstant(row));
502  }
503  }
504  } /* for( c = 0; c < nrows; ++ c) */
505 
506  /* Initialize cut activity */
507  *cutact = 0.0;
508 
509  /* Modify cut to make it numerically safer, and check that it is numerically safe */
510  success = modifyAndPackCut(scip, sepadata, ncols, cols, workcoefs, cutcoefs, cutind, cutnz, cutrhs);
511  if ( success )
512  {
513  success = checkNumerics(scip, sepadata, ncols, cols, cutcoefs, cutind, cutnz, cutrhs, cutact);
514  SCIPdebugMsg(scip, "checkNumerics returned: %u.\n", success);
515  return success;
516  }
517  SCIPdebugMsg(scip, "modifyAndPackCut was not successful.\n");
518 
519  return FALSE;
520 }
521 
522 
523 /*
524  * Callback methods
525  */
526 
527 /** copy method for separator plugins (called when SCIP copies plugins) */
528 static
529 SCIP_DECL_SEPACOPY(sepaCopyGMI)
530 { /*lint --e{715}*/
531  assert(scip != NULL);
532  assert(sepa != NULL);
533  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
534 
535  /* call inclusion method of constraint handler */
536  SCIP_CALL( SCIPincludeSepaGMI(scip) );
537 
538  return SCIP_OKAY;
539 }
540 
541 /** destructor of separator to free user data (called when SCIP is exiting) */
542 static
543 SCIP_DECL_SEPAFREE(sepaFreeGMI)
544 { /*lint --e{715}*/
545  SCIP_SEPADATA* sepadata;
546 
547  assert(scip != NULL);
548  assert(sepa != NULL);
549  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
550 
551  /* free separator data */
552  sepadata = SCIPsepaGetData(sepa);
553  assert(sepadata != NULL);
554 
555  SCIPfreeBlockMemory(scip, &sepadata);
556 
557  SCIPsepaSetData(sepa, NULL);
558 
559  return SCIP_OKAY;
560 }
561 
562 /** LP solution separation method of separator */
563 static
564 SCIP_DECL_SEPAEXECLP(sepaExeclpGMI)
565 { /*lint --e{715}*/
566  char cutname[SCIP_MAXSTRLEN];
567  SCIP_SEPADATA* sepadata;
568  SCIP_VAR** vars;
569  SCIP_COL** cols;
570  SCIP_ROW** rows;
571  SCIP_Real* binvrow;
572  SCIP_Real* binvarow;
573  SCIP_Real* cutcoefs;
574  SCIP_Real* workcoefs;
575  SCIP_Real cutrhs;
576  int* cutind;
577  int* basisind;
578  int nvars;
579  int ncols;
580  int nrows;
581  int ncalls;
582  int depth;
583  int maxsepacuts;
584  int ncuts;
585  int cutnz;
586  int c;
587  int i;
588  int j;
589 
590  assert(sepa != NULL);
591  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
592  assert(scip != NULL);
593  assert(result != NULL);
594 
595  *result = SCIP_DIDNOTRUN;
596 
597  /* Only call separator, if we are not close to terminating. */
598  if( SCIPisStopped(scip) )
599  return SCIP_OKAY;
600 
601  /* Only call separator, if an optimal LP solution is at hand. */
602  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
603  return SCIP_OKAY;
604 
605  /* Only call separator, if the LP solution is basic. */
606  if( ! SCIPisLPSolBasic(scip) )
607  return SCIP_OKAY;
608 
609  /* Only call separator, if there are fractional variables. */
610  if( SCIPgetNLPBranchCands(scip) == 0 )
611  return SCIP_OKAY;
612 
613  sepadata = SCIPsepaGetData(sepa);
614  assert(sepadata != NULL);
615 
616  depth = SCIPgetDepth(scip);
617  ncalls = SCIPsepaGetNCallsAtNode(sepa);
618 
619  /* Only call the gomory cut separator a given number of times at each node. */
620  if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot) || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
621  return SCIP_OKAY;
622 
623  /* get variables data */
624  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
625 
626  /* get LP data */
627  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
628  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
629 
630  /* exit if LP is trivial */
631  if( ncols == 0 || nrows == 0 )
632  return SCIP_OKAY;
633 
634  *result = SCIP_DIDNOTFIND;
635 
636  /* allocate temporary memory */
637  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
638  SCIP_CALL( SCIPallocBufferArray(scip, &workcoefs, ncols) );
639  SCIP_CALL( SCIPallocBufferArray(scip, &cutind, ncols) );
640  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
641  SCIP_CALL( SCIPallocBufferArray(scip, &binvarow, ncols) );
642  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
643 
644  /* get basis indices */
645  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
646 
647  /* get the maximal number of cuts allowed in a separation round */
648  if( depth == 0 )
649  maxsepacuts = sepadata->maxsepacutsroot;
650  else
651  maxsepacuts = sepadata->maxsepacuts;
652 
653  if( maxsepacuts == -1 )
654  maxsepacuts = INT_MAX;
655 
656  /* For all basic columns belonging to integer variables, try to generate a gomory cut. */
657  ncuts = 0;
658  for( i = 0; i < nrows && ncuts < maxsepacuts && ! SCIPisStopped(scip) && *result != SCIP_CUTOFF; ++i )
659  {
660  SCIP_Bool tryrow;
661  SCIP_Real primsol;
662 
663  tryrow = FALSE;
664  c = basisind[i];
665  primsol = SCIP_INVALID;
666 
667  SCIPdebugMsg(scip, "Row %d basic variable %d with value %f\n", i, basisind[i], (c >= 0) ? SCIPcolGetPrimsol(cols[c]) : SCIPgetRowActivity(scip, rows[-c-1]));
668  if( c >= 0 )
669  {
670  SCIP_VAR* var;
671  assert(c < ncols);
672  assert(cols[c] != NULL);
673  var = SCIPcolGetVar(cols[c]);
674  if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
675  {
676  primsol = SCIPcolGetPrimsol(cols[c]);
677  assert(SCIPgetVarSol(scip, var) == primsol); /*lint !e777*/
678 
679  if( (SCIPfeasFrac(scip, primsol) >= sepadata->away) && (SCIPfeasFrac(scip, primsol) <= 1 - sepadata->away) )
680  {
681  SCIPdebugMsg(scip, "trying gomory cut for col <%s> [%g] row %i\n", SCIPvarGetName(var), primsol, i);
682  tryrow = TRUE;
683  }
684  }
685  }
686  else if( sepadata->separaterows )
687  {
688  SCIP_ROW* row;
689  assert(0 <= -c-1 && -c-1 < nrows);
690  row = rows[-c-1];
691  if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
692  {
693  /* Compute value of the slack variable (we only care about the correct fractionality) */
694  if ( SCIPisInfinity(scip, SCIProwGetRhs(row)) )
695  primsol = SCIProwGetLhs(row) - SCIPgetRowLPActivity(scip, row);
696  else
697  primsol = SCIProwGetRhs(row) - SCIPgetRowLPActivity(scip, row);
698 
699  if( (SCIPfeasFrac(scip, primsol) >= sepadata->away) && (SCIPfeasFrac(scip, primsol) <= 1 - sepadata->away) )
700  {
701  SCIPdebugMsg(scip, "trying gomory cut for row <%s> [%g]\n", SCIProwGetName(row), primsol);
702  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
703  tryrow = TRUE;
704  }
705  }
706  }
707 
708  if( tryrow )
709  {
710  SCIP_Real cutact;
711  SCIP_Bool success;
712  SCIP_Bool cutislocal;
713 
714  /* dummy data structures for sparsity information */
715  int* inds = NULL;
716  int ninds = -1;
717 
718  /* get the row of B^-1 for this basic integer variable with fractional solution value */
719  SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow, inds, &ninds) );
720 
721  /* get the tableau row for this basic integer variable with fractional solution value */
722  SCIP_CALL( SCIPgetLPBInvARow(scip, i, binvrow, binvarow, inds, &ninds) );
723 
724  /* this is an approximation (one could also pass over coefficients and check whether local rows have been used): */
725  cutislocal = (depth != 0) ? TRUE : FALSE;
726 
727  /* create a GMI cut out of the simplex tableau row */
728  success = getGMIFromRow(scip, sepadata, ncols, nrows, cols, rows, binvrow, binvarow, primsol, cutcoefs, cutind, &cutnz, &cutrhs, &cutact, workcoefs);
729 
730  SCIPdebugMsg(scip, " -> success = %u: %g <= %g\n", success, cutact, cutrhs);
731 
732  /* if successful, add the row as a cut */
733  if( success )
734  {
735  SCIP_ROW* cut;
736 
737  /* construct cut name */
738  if( c >= 0 )
739  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gmi%d_x%d", SCIPgetNLPs(scip), c);
740  else
741  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gmi%d_s%d", SCIPgetNLPs(scip), -c-1);
742 
743  /* create empty cut */
744  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
745 
746  /* cache the row extension and only flush them if the cut gets added */
747  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
748 
749  /* collect all non-zero coefficients */
750  for( j = 0; j < cutnz; ++j )
751  {
752  SCIP_CALL( SCIPaddVarToRow(scip, cut, SCIPcolGetVar(cols[cutind[j]]), cutcoefs[j]) );
753  }
754 
755  if( SCIProwGetNNonz(cut) == 0 )
756  {
757  assert(SCIPisFeasNegative(scip, cutrhs));
758  SCIPdebugMsg(scip, " -> gomory cut detected infeasibility with cut 0 <= %f\n", cutrhs);
759  *result = SCIP_CUTOFF;
760  break;
761  }
762 
763  /* Only take efficacious cuts, except for cuts with one non-zero coefficient (= bound
764  changes); the latter cuts will be handeled internally in sepastore. */
765  if( SCIProwGetNNonz(cut) == 1 || SCIPisCutEfficacious(scip, NULL, cut) )
766  {
767  SCIP_Bool infeasible;
768 
769  SCIPdebugMsg(scip, " -> gomory cut for <%s>: act=%f, rhs=%f, eff=%f\n",
770  c >= 0 ? SCIPvarGetName(SCIPcolGetVar(cols[c])) : SCIProwGetName(rows[-c-1]),
771  cutact, cutrhs, SCIPgetCutEfficacy(scip, NULL, cut));
772 
773  SCIPdebugMsg(scip, " -> found gomory cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
774  cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
775  SCIPgetCutEfficacy(scip, NULL, cut),
776  SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
777  SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
778 
779  /* flush all changes before adding the cut */
780  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
781 
782  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, &infeasible) );
783 
784  /* add global cuts that are not implicit bound changes to the cut pool */
785  if( ! cutislocal && SCIProwGetNNonz(cut) > 1 )
786  {
787  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
788  }
789 
790  if ( infeasible )
791  *result = SCIP_CUTOFF;
792  else
793  *result = SCIP_SEPARATED;
794  ncuts++;
795  }
796 
797  /* release the row */
798  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
799  }
800  }
801  }
802 
803  /* free temporary memory */
804  SCIPfreeBufferArray(scip, &binvarow);
805  SCIPfreeBufferArray(scip, &binvrow);
806  SCIPfreeBufferArray(scip, &basisind);
807  SCIPfreeBufferArray(scip, &workcoefs);
808  SCIPfreeBufferArray(scip, &cutcoefs);
809  SCIPfreeBufferArray(scip, &cutind);
810 
811  SCIPdebugMsg(scip, "end searching gomory cuts: found %d cuts.\n", ncuts);
812 
813  sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
814 
815  return SCIP_OKAY;
816 }
817 
818 
819 /*
820  * separator specific interface methods
821  */
822 
823 /** creates the GMI MIR cut separator and includes it in SCIP */
824 SCIP_RETCODE SCIPincludeSepaGMI(
825  SCIP* scip /**< SCIP data structure */
826  )
827 {
828  SCIP_SEPADATA* sepadata;
829  SCIP_SEPA* sepa;
830 
831  /* create separator data */
832  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
833  sepadata->lastncutsfound = 0;
834 
835  /* include separator */
836  SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
837  SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpGMI, NULL, sepadata) );
838 
839  assert(sepa != NULL);
840 
841  /* set non-NULL pointers to callback methods */
842  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyGMI) );
843  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeGMI) );
844 
845  /* add separator parameters */
846  SCIP_CALL( SCIPaddIntParam(scip,
847  "separating/gmi/maxrounds",
848  "maximal number of gmi separation rounds per node (-1: unlimited)",
849  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
850  SCIP_CALL( SCIPaddIntParam(scip,
851  "separating/gmi/maxroundsroot",
852  "maximal number of gmi separation rounds in the root node (-1: unlimited)",
853  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
854  SCIP_CALL( SCIPaddIntParam(scip,
855  "separating/gmi/maxsepacuts",
856  "maximal number of gmi cuts separated per separation round (-1: unlimited)",
857  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, -1, INT_MAX, NULL, NULL) );
858  SCIP_CALL( SCIPaddIntParam(scip,
859  "separating/gmi/maxsepacutsroot",
860  "maximal number of gmi cuts separated per separation round in the root node (-1: unlimited)",
861  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, -1, INT_MAX, NULL, NULL) );
862  SCIP_CALL( SCIPaddBoolParam(scip,
863  "separating/gmi/dynamiccuts",
864  "should generated cuts be removed from the LP if they are no longer tight?",
865  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
866  SCIP_CALL( SCIPaddBoolParam(scip,
867  "separating/gmi/separaterows",
868  "separate rows with integral slack",
869  &sepadata->separaterows, FALSE, DEFAULT_SEPARATEROWS, NULL, NULL) );
870  SCIP_CALL( SCIPaddRealParam(scip,
871  "separating/gmi/away",
872  "minimal fractionality of a basic variable in order to try GMI cut",
873  &sepadata->away, FALSE, AWAY, 0.0, 0.5, NULL, NULL) );
874  SCIP_CALL( SCIPaddRealParam(scip,
875  "separating/gmi/minviolation",
876  "minimal violation to accept cut",
877  &sepadata->minviolation, FALSE, MIN_VIOLATION, 0.0, 1.0, NULL, NULL) );
878  SCIP_CALL( SCIPaddRealParam(scip,
879  "separating/gmi/epscoeff",
880  "tolerance for zeroing out small coefficients",
881  &sepadata->epscoeff, FALSE, EPS_COEFF, 0.0, 0.01, NULL, NULL) );
882  SCIP_CALL( SCIPaddRealParam(scip,
883  "separating/gmi/epsrelaxabs",
884  "absolute cut rhs relaxation",
885  &sepadata->epsrelaxabs, FALSE, EPS_RELAX_ABS, 0.0, SCIP_REAL_MAX, NULL, NULL) );
886  SCIP_CALL( SCIPaddRealParam(scip,
887  "separating/gmi/epsrelaxrel",
888  "relative cut rhs relaxation",
889  &sepadata->epsrelaxrel, FALSE, EPS_RELAX_REL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
890  SCIP_CALL( SCIPaddRealParam(scip,
891  "separating/gmi/maxdynamism",
892  "maximal valid range max(|weights|)/min(|weights|) of cut coefficients",
893  &sepadata->maxdynamism, FALSE, MAX_DYN, 0.0, SCIP_REAL_MAX, NULL, NULL) );
894  SCIP_CALL( SCIPaddIntParam(scip,
895  "separating/gmi/maxsuppabs",
896  "maximum cut support - absolute value in the formula",
897  &sepadata->maxsuppabs, FALSE, MAX_SUPP_ABS, 0, INT_MAX, NULL, NULL) );
898  SCIP_CALL( SCIPaddRealParam(scip,
899  "separating/gmi/maxsupprel",
900  "maximum cut support - relative value in the formula",
901  &sepadata->maxsupprel, FALSE, MAX_SUPP_REL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
902 
903  return SCIP_OKAY;
904 }
SCIPisFeasZero
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47357
SCIP_DIDNOTRUN
Definition: type_result.h:33
SCIPgetLPBInvRow
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29778
SCIPcacheRowExtensions
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30607
SCIPflushRowExtensions
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30630
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:259
SCIP_DECL_SEPACOPY
static SCIP_DECL_SEPACOPY(sepaCopyGMI)
Definition: sepa_gmi.c:529
SCIPcolGetBasisStatus
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:16240
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30662
SCIProwGetNNonz
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16402
DEFAULT_SEPARATEROWS
#define DEFAULT_SEPARATEROWS
Definition: sepa_gmi.c:83
SCIP_DECL_SEPAFREE
static SCIP_DECL_SEPAFREE(sepaFreeGMI)
Definition: sepa_gmi.c:543
SCIProwGetName
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16540
SCIP_Var
Definition: struct_var.h:198
SCIPisFeasNegative
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47381
SCIProwGetNLPNonz
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:16416
SCIPgetVarsData
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
SCIProwGetLhs
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16481
FALSE
#define FALSE
Definition: def.h:64
SCIPcolIsIntegral
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:16271
SCIPcolGetUb
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:16182
SCIProwGetBasisStatus
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:16529
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
TRUE
#define TRUE
Definition: def.h:63
SCIPdebug
#define SCIPdebug(x)
Definition: pub_message.h:74
SCIPsepaGetName
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:646
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
MAX_SUPP_REL
#define MAX_SUPP_REL
Definition: sepa_gmi.c:92
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_SEPARATED
Definition: type_result.h:40
SCIPfeasFrac
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:47453
SCIP_Sepa
Definition: struct_sepa.h:37
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIPgetLPColsData
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip.c:29556
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:37028
SCIPsetSepaCopy
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip.c:7427
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip.h:455
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.c:4265
SCIPgetRowMaxCoef
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30883
SCIPsepaGetData
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:557
SCIP_Col
Definition: struct_lp.h:126
MIN_VIOLATION
#define MIN_VIOLATION
Definition: sepa_gmi.c:86
DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_gmi.c:81
SCIPisLPSolBasic
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29731
EPS_COEFF
#define EPS_COEFF
Definition: sepa_gmi.c:87
SCIPisCutEfficacious
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:34522
modifyAndPackCut
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
SCIPcolGetPrimsol
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16205
SCIPgetRowMinCoef
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30865
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIPgetNCutsFound
int SCIPgetNCutsFound(SCIP *scip)
Definition: scip.c:42896
SCIPsepaGetNCallsAtNode
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:773
SEPA_NAME
#define SEPA_NAME
Definition: sepa_gmi.c:70
SCIP_DECL_SEPAEXECLP
static SCIP_DECL_SEPAEXECLP(sepaExeclpGMI)
Definition: sepa_gmi.c:564
SCIPcolGetLb
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:16172
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIProwIsIntegral
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:16580
SCIPsepaSetData
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:567
REALABS
#define REALABS(x)
Definition: def.h:173
SCIP_OKAY
Definition: type_retcode.h:33
MAX_SUPP_ABS
#define MAX_SUPP_ABS
Definition: sepa_gmi.c:91
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:350
SCIPincludeSepaGMI
SCIP_RETCODE SCIPincludeSepaGMI(SCIP *scip)
Definition: sepa_gmi.c:824
SCIProwGetRhs
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16491
SCIPgetRowLPActivity
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30954
SCIPaddRow
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:34655
SCIProwIsModifiable
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:16600
SCIProwGetCols
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16427
SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:34
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.c:7385
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIPgetLPBInvARow
SCIP_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29849
SCIProwGetVals
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16437
pub_misc.h
public data structures and miscellaneous methods
DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_gmi.c:79
SCIP_Bool
#define SCIP_Bool
Definition: def.h:61
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
getGMIFromRow
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:269
sepa_gmi.h
Gomory Mixed-Integer Cuts.
checkNumerics
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
DEFAULT_DYNAMICCUTS
#define DEFAULT_DYNAMICCUTS
Definition: sepa_gmi.c:82
SCIPgetDepth
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP
Definition: sepa_gmi.c:75
MAX
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_Row
Definition: struct_lp.h:192
SCIPaddPoolCut
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:34766
DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS
Definition: sepa_gmi.c:78
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.c:30425
SCIPgetCutEfficacy
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:34499
SEPA_DELAY
#define SEPA_DELAY
Definition: sepa_gmi.c:76
SCIPgetLPBasisInd
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip.c:29750
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
SEPA_FREQ
#define SEPA_FREQ
Definition: sepa_gmi.c:73
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:150
SEPA_PRIORITY
#define SEPA_PRIORITY
Definition: sepa_gmi.c:72
SCIProwGetConstant
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16447
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30534
SCIPsetSepaFree
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip.c:7443
SCIPcolGetVar
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16251
SCIP_BASESTAT_LOWER
Definition: type_lpi.h:81
SCIProwGetLPPos
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:16670
SCIP_Real
#define SCIP_Real
Definition: def.h:149
SEPA_DESC
#define SEPA_DESC
Definition: sepa_gmi.c:71
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST
Definition: sepa_gmi.c:74
SCIP_INVALID
#define SCIP_INVALID
Definition: def.h:169
SCIPprintRow
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:31154
SCIPfrac
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:47179
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47070
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46983
SCIPgetVarSol
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:19826
EPS_RELAX_ABS
#define EPS_RELAX_ABS
Definition: sepa_gmi.c:88
SCIP_BASESTAT_BASIC
Definition: type_lpi.h:82
AWAY
#define AWAY
Definition: sepa_gmi.c:85
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIPgetLPRowsData
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29634
SCIPgetNLPs
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:42308
SCIPcolGetLPPos
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16292
SCIP_BASESTAT_ZERO
Definition: type_lpi.h:84
SCIProwGetNorm
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:16457
DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXSEPACUTS
Definition: sepa_gmi.c:80
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.c:4321
SCIP_BASESTAT_UPPER
Definition: type_lpi.h:83
EPSZ
#define EPSZ(x, eps)
Definition: def.h:179
EPS_RELAX_REL
#define EPS_RELAX_REL
Definition: sepa_gmi.c:89
SCIP_CUTOFF
Definition: type_result.h:39
SCIP_SEPADATA
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:38
MAX_DYN
#define MAX_DYN
Definition: sepa_gmi.c:90
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.c:4239
SCIPgetRowActivity
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:31065
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:58