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