Scippy

SCIP

Solving Constraint Integer Programs

sepa_gomory.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-2014 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 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sepa_gomory.c
17  * @brief Gomory MIR Cuts
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  * @author Domenico Salvagnin
21  * @author Marc Pfetsch
22  */
23 
24 /**@todo try k-Gomory-cuts (s. Cornuejols: K-Cuts: A Variation of Gomory Mixed Integer Cuts from the LP Tableau)
25  *
26  * @todo Try cuts on the objective tableau row.
27  *
28  * @todo Also try negative basis inverse row?
29  *
30  * @todo It happens that the SCIPcalcMIR() function returns with the same cut for different calls. Check if this is a
31  * bug or do not use it for the MIP below and turn off presolving and all heuristics:
32  *
33  * Max y
34  * Subject to
35  * c1: -x + y <= 1
36  * c2: 2x + 3y <= 12
37  * c3: 3x + 2y <= 12
38  * Bounds
39  * 0 <= x
40  * 0 <= y
41  * General
42  * x
43  * y
44  * END
45  */
46 
47 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
48 
49 #include <assert.h>
50 #include <string.h>
51 
52 #include "scip/sepa_gomory.h"
53 #include "scip/pub_misc.h"
54 #include "scip/pub_lp.h"
55 
56 #define SEPA_NAME "gomory"
57 #define SEPA_DESC "Gomory MIR cuts separator"
58 #define SEPA_PRIORITY -1000
59 #define SEPA_FREQ 0
60 #define SEPA_MAXBOUNDDIST 0.0
61 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
62 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
63 
64 #define DEFAULT_MAXROUNDS 5 /**< maximal number of gomory separation rounds per node (-1: unlimited) */
65 #define DEFAULT_MAXROUNDSROOT 10 /**< maximal number of gomory separation rounds in the root node (-1: unlimited) */
66 #define DEFAULT_MAXSEPACUTS 50 /**< maximal number of gomory cuts separated per separation round */
67 #define DEFAULT_MAXSEPACUTSROOT 200 /**< maximal number of gomory cuts separated per separation round in root node */
68 #define DEFAULT_MAXRANK 3 /**< maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited) */
69 #define DEFAULT_MAXRANKINTEGRAL -1 /**< maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited) */
70 #define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
71 #define DEFAULT_MAXWEIGHTRANGE 1e+04 /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
72 #define DEFAULT_AWAY 0.01 /**< minimal integrality violation of a basis variable in order to try Gomory cut */
73 #define DEFAULT_MAKEINTEGRAL TRUE /**< try to scale all cuts to integral coefficients */
74 #define DEFAULT_FORCECUTS TRUE /**< if conversion to integral coefficients failed still consider the cut */
75 #define DEFAULT_SEPARATEROWS TRUE /**< separate rows with integral slack */
76 #define DEFAULT_DELAYEDCUTS TRUE /**< should cuts be added to the delayed cut pool? */
77 #define DEFAULT_SIDETYPEBASIS FALSE /**< choose side types of row (lhs/rhs) based on basis information? */
78 
79 #define BOUNDSWITCH 0.9999 /**< threshold for bound switching - see SCIPcalcMIR() */
80 #define USEVBDS TRUE /**< use variable bounds - see SCIPcalcMIR() */
81 #define ALLOWLOCAL TRUE /**< allow to generate local cuts - see SCIPcalcMIR() */
82 #define FIXINTEGRALRHS FALSE /**< try to generate an integral rhs - see SCIPcalcMIR() */
83 #define MAKECONTINTEGRAL FALSE /**< convert continuous variable to integral variables in SCIPmakeRowIntegral() */
84 
85 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) /**< maximal length of base inequality */
86 
87 
88 /** separator data */
89 struct SCIP_SepaData
90 {
91  SCIP_Real maxweightrange; /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
92  SCIP_Real away; /**< minimal integrality violation of a basis variable in order to try Gomory cut */
93  int maxrounds; /**< maximal number of gomory separation rounds per node (-1: unlimited) */
94  int maxroundsroot; /**< maximal number of gomory separation rounds in the root node (-1: unlimited) */
95  int maxsepacuts; /**< maximal number of gomory cuts separated per separation round */
96  int maxsepacutsroot; /**< maximal number of gomory cuts separated per separation round in root node */
97  int maxrank; /**< maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited) */
98  int maxrankintegral; /**< maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited) */
99  int lastncutsfound; /**< total number of cuts found after last call of separator */
100  SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
101  SCIP_Bool makeintegral; /**< try to scale all cuts to integral coefficients */
102  SCIP_Bool forcecuts; /**< if conversion to integral coefficients failed still consider the cut */
103  SCIP_Bool separaterows; /**< separate rows with integral slack */
104  SCIP_Bool delayedcuts; /**< should cuts be added to the delayed cut pool? */
105  SCIP_Bool sidetypebasis; /**< choose side types of row (lhs/rhs) based on basis information? */
106 };
107 
108 
109 /** returns TRUE if the cut can be taken, otherwise FALSE if there some numerical evidences */
110 static
111 SCIP_RETCODE evaluateCutNumerics(
112  SCIP* scip, /**< SCIP data structure */
113  SCIP_SEPADATA* sepadata, /**< data of the separator */
114  SCIP_ROW* cut, /**< cut to check */
115  SCIP_Longint maxdnom, /**< maximal denominator to use for scaling */
116  SCIP_Real maxscale, /**< maximal scaling factor */
117  SCIP_Bool* useful /**< pointer to store if the cut is useful */
118  )
119 {
120  SCIP_Bool madeintegral;
121 
122  madeintegral = FALSE;
123  (*useful) = FALSE;
124 
125  if( sepadata->makeintegral )
126  {
127  /* try to scale the cut to integral values */
128  SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
129  maxdnom, maxscale, MAKECONTINTEGRAL, &madeintegral) );
130 
131  if( !madeintegral && !sepadata->forcecuts )
132  return SCIP_OKAY;
133 
134  /* in case the right hand side is plus infinity (due to scaling) the cut is useless so we are not taking it at all
135  */
136  if( madeintegral && SCIPisInfinity(scip, SCIProwGetRhs(cut)) )
137  return SCIP_OKAY;
138  }
139 
140  /* discard integral cut if the rank is too high */
141  if( madeintegral && sepadata->maxrankintegral != -1 && (SCIProwGetRank(cut) > sepadata->maxrankintegral) )
142  return SCIP_OKAY;
143 
144  /* discard cut if the rank is too high */
145  if( !madeintegral && (sepadata->maxrank != -1) && (SCIProwGetRank(cut) > sepadata->maxrank) )
146  return SCIP_OKAY;
147 
148  (*useful) = TRUE;
149 
150  return SCIP_OKAY;
151 }
152 
153 
154 /*
155  * Callback methods
156  */
157 
158 /** copy method for separator plugins (called when SCIP copies plugins) */
159 static
160 SCIP_DECL_SEPACOPY(sepaCopyGomory)
161 { /*lint --e{715}*/
162  assert(scip != NULL);
163  assert(sepa != NULL);
164  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
165 
166  /* call inclusion method of constraint handler */
167  SCIP_CALL( SCIPincludeSepaGomory(scip) );
168 
169  return SCIP_OKAY;
170 }
171 
172 /** destructor of separator to free user data (called when SCIP is exiting) */
173 static
174 SCIP_DECL_SEPAFREE(sepaFreeGomory)
175 { /*lint --e{715}*/
176  SCIP_SEPADATA* sepadata;
177 
178  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
179 
180  /* free separator data */
181  sepadata = SCIPsepaGetData(sepa);
182  assert(sepadata != NULL);
183 
184  SCIPfreeMemory(scip, &sepadata);
185 
186  SCIPsepaSetData(sepa, NULL);
187 
188  return SCIP_OKAY;
189 }
190 
191 
192 /** LP solution separation method of separator */
193 static
194 SCIP_DECL_SEPAEXECLP(sepaExeclpGomory)
195 { /*lint --e{715}*/
196  SCIP_SEPADATA* sepadata;
197  SCIP_VAR** vars;
198  SCIP_COL** cols;
199  SCIP_ROW** rows;
200  SCIP_Real* binvrow;
201  SCIP_Real* cutcoefs;
202  SCIP_Real maxscale;
203  SCIP_Real minfrac;
204  SCIP_Real maxfrac;
205  SCIP_Longint maxdnom;
206  SCIP_Bool cutoff;
207  int* sidetypes = NULL;
208  int* basisind;
209  int naddedcuts;
210  int nvars;
211  int ncols;
212  int nrows;
213  int ncalls;
214  int depth;
215  int maxdepth;
216  int maxsepacuts;
217  int c;
218  int i;
219 
220  assert(sepa != NULL);
221  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
222  assert(scip != NULL);
223  assert(result != NULL);
224 
225  *result = SCIP_DIDNOTRUN;
226 
227  sepadata = SCIPsepaGetData(sepa);
228  assert(sepadata != NULL);
229 
230  depth = SCIPgetDepth(scip);
231  ncalls = SCIPsepaGetNCallsAtNode(sepa);
232 
233  minfrac = sepadata->away;
234  maxfrac = 1.0 - sepadata->away;
235 
236  /* only call separator, if we are not close to terminating */
237  if( SCIPisStopped(scip) )
238  return SCIP_OKAY;
239 
240  /* only call the gomory cut separator a given number of times at each node */
241  if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
242  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
243  return SCIP_OKAY;
244 
245  /* only call separator, if an optimal LP solution is at hand */
246  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
247  return SCIP_OKAY;
248 
249  /* only call separator, if the LP solution is basic */
250  if( !SCIPisLPSolBasic(scip) )
251  return SCIP_OKAY;
252 
253  /* only call separator, if there are fractional variables */
254  if( SCIPgetNLPBranchCands(scip) == 0 )
255  return SCIP_OKAY;
256 
257  /* get variables data */
258  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
259 
260  /* get LP data */
261  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
262  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
263  if( ncols == 0 || nrows == 0 )
264  return SCIP_OKAY;
265 
266 #if 0 /* if too many columns, separator is usually very slow: delay it until no other cuts have been found */
267  if( ncols >= 50*nrows )
268  return SCIP_OKAY;
269 
270  if( ncols >= 5*nrows )
271  {
272  int ncutsfound;
273 
274  ncutsfound = SCIPgetNCutsFound(scip);
275  if( ncutsfound > sepadata->lastncutsfound || !SCIPsepaWasLPDelayed(sepa) )
276  {
277  sepadata->lastncutsfound = ncutsfound;
278  *result = SCIP_DELAYED;
279  return SCIP_OKAY;
280  }
281  }
282 #endif
283 
284  /* set the maximal denominator in rational representation of gomory cut and the maximal scale factor to
285  * scale resulting cut to integral values to avoid numerical instabilities
286  */
287  /**@todo find better but still stable gomory cut settings: look at dcmulti, gesa3, khb0525, misc06, p2756 */
288  maxdepth = SCIPgetMaxDepth(scip);
289  if( depth == 0 )
290  {
291  maxdnom = 1000;
292  maxscale = 1000.0;
293  }
294  else if( depth <= maxdepth/4 )
295  {
296  maxdnom = 1000;
297  maxscale = 1000.0;
298  }
299  else if( depth <= maxdepth/2 )
300  {
301  maxdnom = 100;
302  maxscale = 100.0;
303  }
304  else
305  {
306  maxdnom = 10;
307  maxscale = 10.0;
308  }
309 
310  /* allocate temporary memory */
311  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
312  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
313  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
314  if ( sepadata->sidetypebasis )
315  {
316  SCIP_CALL( SCIPallocBufferArray(scip, &sidetypes, nrows) );
317  }
318 
319  /* get basis indices */
320  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
321 
322  /* get the maximal number of cuts allowed in a separation round */
323  if( depth == 0 )
324  maxsepacuts = sepadata->maxsepacutsroot;
325  else
326  maxsepacuts = sepadata->maxsepacuts;
327 
328  SCIPdebugMessage("searching gomory cuts: %d cols, %d rows, maxdnom=%"SCIP_LONGINT_FORMAT", maxscale=%g, maxcuts=%d\n",
329  ncols, nrows, maxdnom, maxscale, maxsepacuts);
330 
331  cutoff = FALSE;
332  naddedcuts = 0;
333 
334  /* for all basic columns belonging to integer variables, try to generate a gomory cut */
335  for( i = 0; i < nrows && naddedcuts < maxsepacuts && !SCIPisStopped(scip) && !cutoff; ++i )
336  {
337  SCIP_Bool tryrow;
338 
339  tryrow = FALSE;
340  c = basisind[i];
341  if( c >= 0 )
342  {
343  SCIP_VAR* var;
344 
345  assert(c < ncols);
346  var = SCIPcolGetVar(cols[c]);
347  if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
348  {
349  SCIP_Real primsol;
350 
351  primsol = SCIPcolGetPrimsol(cols[c]);
352  assert(SCIPgetVarSol(scip, var) == primsol); /*lint !e777*/
353 
354  if( SCIPfeasFrac(scip, primsol) >= minfrac )
355  {
356  SCIPdebugMessage("trying gomory cut for col <%s> [%g]\n", SCIPvarGetName(var), primsol);
357  tryrow = TRUE;
358  }
359  }
360  }
361  else if( sepadata->separaterows )
362  {
363  SCIP_ROW* row;
364 
365  assert(0 <= -c-1 && -c-1 < nrows);
366  row = rows[-c-1];
367  if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
368  {
369  SCIP_Real primsol;
370 
371  primsol = SCIPgetRowActivity(scip, row);
372  if( SCIPfeasFrac(scip, primsol) >= minfrac )
373  {
374  SCIPdebugMessage("trying gomory cut for row <%s> [%g]\n", SCIProwGetName(row), primsol);
375  tryrow = TRUE;
376  }
377  }
378  }
379 
380  if( tryrow )
381  {
382  SCIP_Real cutrhs;
383  SCIP_Real cutact;
384  SCIP_Bool success;
385  SCIP_Bool cutislocal;
386  int cutrank;
387 
388  /* get the row of B^-1 for this basic integer variable with fractional solution value */
389  SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow) );
390 
391  if ( sepadata->sidetypebasis )
392  {
393  int k;
394 
395  assert( sidetypes != NULL );
396  for (k = 0; k < nrows; ++k)
397  {
398  SCIP_BASESTAT stat;
399  SCIP_ROW* row;
400 
401  row = rows[k];
402  assert( row != NULL );
403 
404  /* for equations take automatic choice */
405  if ( SCIPisEQ(scip, SCIProwGetLhs(row), SCIProwGetRhs(row)) )
406  sidetypes[k] = 0;
407  else
408  {
409  /* for ranged rows use basis status */
410  assert( SCIPisLPSolBasic(scip) );
411  stat = SCIProwGetBasisStatus(row);
412  if ( stat == SCIP_BASESTAT_LOWER )
413  {
414  assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
415  sidetypes[k] = -1;
416  }
417  else if ( stat == SCIP_BASESTAT_UPPER )
418  {
419  assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) );
420  sidetypes[k] = 1;
421  }
422  else
423  sidetypes[k] = 0;
424  }
425  }
426  }
427 
428  cutact = 0.0;
429  cutrhs = SCIPinfinity(scip);
430 
431  /* create a MIR cut out of the weighted LP rows using the B^-1 row as weights */
432  SCIP_CALL( SCIPcalcMIR(scip, NULL, BOUNDSWITCH, USEVBDS, ALLOWLOCAL, FIXINTEGRALRHS, NULL, NULL,
433  (int) MAXAGGRLEN(nvars), sepadata->maxweightrange, minfrac, maxfrac,
434  binvrow, sidetypes, 1.0, NULL, NULL, cutcoefs, &cutrhs, &cutact, &success, &cutislocal, &cutrank) );
435  assert(ALLOWLOCAL || !cutislocal);
436 
437  /* @todo Currently we are using the SCIPcalcMIR() function to compute the coefficients of the Gomory
438  * cut. Alternatively, we could use the direct version (see thesis of Achterberg formula (8.4)) which
439  * leads to cut a of the form \sum a_i x_i \geq 1. Rumor has it that these cuts are better.
440  */
441 
442  SCIPdebugMessage(" -> success=%u: %g <= %g\n", success, cutact, cutrhs);
443 
444  /* if successful, convert dense cut into sparse row, and add the row as a cut */
445  if( success && SCIPisFeasGT(scip, cutact, cutrhs) )
446  {
447  SCIP_ROW* cut;
448  char cutname[SCIP_MAXSTRLEN];
449  int v;
450 
451  /* construct cut name */
452  if( c >= 0 )
453  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gom%d_x%d", SCIPgetNLPs(scip), c);
454  else
455  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gom%d_s%d", SCIPgetNLPs(scip), -c-1);
456 
457  /* create empty cut */
458  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs,
459  cutislocal, FALSE, sepadata->dynamiccuts) );
460 
461  /* set cut rank */
462  SCIProwChgRank(cut, cutrank);
463 
464  /* cache the row extension and only flush them if the cut gets added */
465  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
466 
467  /* collect all non-zero coefficients */
468  for( v = 0; v < nvars; ++v )
469  {
470  if( !SCIPisZero(scip, cutcoefs[v]) )
471  {
472  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[v], cutcoefs[v]) );
473  }
474  }
475 
476  if( SCIProwGetNNonz(cut) == 0 )
477  {
478  assert(SCIPisFeasNegative(scip, cutrhs));
479  SCIPdebugMessage(" -> gomory cut detected infeasibility with cut 0 <= %f\n", cutrhs);
480  cutoff = TRUE;
481  }
482  else if( SCIProwGetNNonz(cut) == 1 )
483  {
484  /* add the bound change as cut to avoid that the LP gets modified. that would mean the LP is not flushed
485  * and the method SCIPgetLPBInvRow() fails; SCIP internally will apply that bound change automatically
486  */
487  SCIP_CALL( SCIPaddCut(scip, NULL, cut, TRUE, &cutoff) );
488  naddedcuts++;
489  }
490  else
491  {
492  /* Only take efficacious cuts, except for cuts with one non-zero coefficients (= bound
493  * changes); the latter cuts will be handeled internally in sepastore.
494  */
495  if( SCIPisCutEfficacious(scip, NULL, cut) )
496  {
497  SCIP_Bool useful;
498 
499  assert(success == TRUE);
500  assert(SCIPisInfinity(scip, -SCIProwGetLhs(cut)));
501  assert(!SCIPisInfinity(scip, SCIProwGetRhs(cut)));
502 
503  SCIPdebugMessage(" -> gomory cut for <%s>: act=%f, rhs=%f, eff=%f\n",
504  c >= 0 ? SCIPvarGetName(SCIPcolGetVar(cols[c])) : SCIProwGetName(rows[-c-1]),
505  cutact, cutrhs, SCIPgetCutEfficacy(scip, NULL, cut));
506 
507  SCIP_CALL( evaluateCutNumerics(scip, sepadata, cut, maxdnom, maxscale, &useful) );
508 
509  if( useful )
510  {
511  SCIPdebugMessage(" -> found gomory cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
512  cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
513  SCIPgetCutEfficacy(scip, NULL, cut),
514  SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
515  SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
516 
517  /* flush all changes before adding the cut */
518  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
519 
520  /* add global cuts which are not implicit bound changes to the cut pool */
521  if( !cutislocal )
522  {
523  if( sepadata->delayedcuts )
524  {
525  SCIP_CALL( SCIPaddDelayedPoolCut(scip, cut) );
526  }
527  else
528  {
529  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
530  }
531  }
532  else
533  {
534  /* local cuts we add to the sepastore */
535  SCIP_CALL( SCIPaddCut(scip, NULL, cut, FALSE, &cutoff) );
536  }
537 
538  naddedcuts++;
539  }
540  }
541  }
542 
543  /* release the row */
544  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
545  }
546  }
547  }
548 
549  /* free temporary memory */
550  if ( sepadata->sidetypebasis )
551  {
552  SCIPfreeBufferArray(scip, &sidetypes);
553  }
554  SCIPfreeBufferArray(scip, &binvrow);
555  SCIPfreeBufferArray(scip, &basisind);
556  SCIPfreeBufferArray(scip, &cutcoefs);
557 
558  SCIPdebugMessage("end searching gomory cuts: found %d cuts\n", naddedcuts);
559 
560  sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
561 
562  /* evalute the result of the separation */
563  if( cutoff )
564  *result = SCIP_CUTOFF;
565  else if ( naddedcuts > 0 )
566  *result = SCIP_SEPARATED;
567  else
568  *result = SCIP_DIDNOTFIND;
569 
570  return SCIP_OKAY;
571 }
572 
573 
574 /*
575  * separator specific interface methods
576  */
577 
578 /** creates the Gomory MIR cut separator and includes it in SCIP */
579 SCIP_RETCODE SCIPincludeSepaGomory(
580  SCIP* scip /**< SCIP data structure */
581  )
582 {
583  SCIP_SEPADATA* sepadata;
584  SCIP_SEPA* sepa;
585 
586  /* create separator data */
587  SCIP_CALL( SCIPallocMemory(scip, &sepadata) );
588  sepadata->lastncutsfound = 0;
589 
590  /* include separator */
591  SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
592  SEPA_USESSUBSCIP, SEPA_DELAY,
593  sepaExeclpGomory, NULL,
594  sepadata) );
595 
596  assert(sepa != NULL);
597 
598  /* set non-NULL pointers to callback methods */
599  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyGomory) );
600  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeGomory) );
601 
602  /* add separator parameters */
603  SCIP_CALL( SCIPaddIntParam(scip,
604  "separating/gomory/maxrounds",
605  "maximal number of gomory separation rounds per node (-1: unlimited)",
606  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
607  SCIP_CALL( SCIPaddIntParam(scip,
608  "separating/gomory/maxroundsroot",
609  "maximal number of gomory separation rounds in the root node (-1: unlimited)",
610  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
611  SCIP_CALL( SCIPaddIntParam(scip,
612  "separating/gomory/maxsepacuts",
613  "maximal number of gomory cuts separated per separation round",
614  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
615  SCIP_CALL( SCIPaddIntParam(scip,
616  "separating/gomory/maxsepacutsroot",
617  "maximal number of gomory cuts separated per separation round in the root node",
618  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
619  SCIP_CALL( SCIPaddIntParam(scip,
620  "separating/gomory/maxrank",
621  "maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited)",
622  &sepadata->maxrank, FALSE, DEFAULT_MAXRANK, -1, INT_MAX, NULL, NULL) );
623  SCIP_CALL( SCIPaddIntParam(scip,
624  "separating/gomory/maxrankintegral",
625  "maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited)",
626  &sepadata->maxrankintegral, FALSE, DEFAULT_MAXRANKINTEGRAL, -1, INT_MAX, NULL, NULL) );
627  SCIP_CALL( SCIPaddRealParam(scip,
628  "separating/gomory/away",
629  "minimal integrality violation of a basis variable in order to try Gomory cut",
630  &sepadata->away, FALSE, DEFAULT_AWAY, 1e-4, 0.5, NULL, NULL) );
631  SCIP_CALL( SCIPaddRealParam(scip,
632  "separating/gomory/maxweightrange",
633  "maximal valid range max(|weights|)/min(|weights|) of row weights",
634  &sepadata->maxweightrange, TRUE, DEFAULT_MAXWEIGHTRANGE, 1.0, SCIP_REAL_MAX, NULL, NULL) );
635  SCIP_CALL( SCIPaddBoolParam(scip,
636  "separating/gomory/dynamiccuts",
637  "should generated cuts be removed from the LP if they are no longer tight?",
638  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
639  SCIP_CALL( SCIPaddBoolParam(scip,
640  "separating/gomory/makeintegral",
641  "try to scale cuts to integral coefficients",
642  &sepadata->makeintegral, TRUE, DEFAULT_MAKEINTEGRAL, NULL, NULL) );
643  SCIP_CALL( SCIPaddBoolParam(scip,
644  "separating/gomory/forcecuts",
645  "if conversion to integral coefficients failed still consider the cut",
646  &sepadata->forcecuts, TRUE, DEFAULT_FORCECUTS, NULL, NULL) );
647  SCIP_CALL( SCIPaddBoolParam(scip,
648  "separating/gomory/separaterows",
649  "separate rows with integral slack",
650  &sepadata->separaterows, TRUE, DEFAULT_SEPARATEROWS, NULL, NULL) );
651  SCIP_CALL( SCIPaddBoolParam(scip,
652  "separating/gomory/delayedcuts",
653  "should cuts be added to the delayed cut pool?",
654  &sepadata->delayedcuts, TRUE, DEFAULT_DELAYEDCUTS, NULL, NULL) );
655  SCIP_CALL( SCIPaddBoolParam(scip,
656  "separating/gomory/sidetypebasis",
657  "choose side types of row (lhs/rhs) based on basis information?",
658  &sepadata->sidetypebasis, TRUE, DEFAULT_SIDETYPEBASIS, NULL, NULL) );
659 
660  return SCIP_OKAY;
661 }
662