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-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 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
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 10
60 #define SEPA_MAXBOUNDDIST 1.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 -1 /**< 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_AWAY 0.01 /**< minimal integrality violation of a basis variable in order to try Gomory cut */
72 #define DEFAULT_MAKEINTEGRAL FALSE /**< try to scale all cuts to integral coefficients */
73 #define DEFAULT_FORCECUTS TRUE /**< if conversion to integral coefficients failed still consider the cut */
74 #define DEFAULT_SEPARATEROWS TRUE /**< separate rows with integral slack */
75 #define DEFAULT_DELAYEDCUTS FALSE /**< should cuts be added to the delayed cut pool? */
76 #define DEFAULT_SIDETYPEBASIS TRUE /**< choose side types of row (lhs/rhs) based on basis information? */
77 #define DEFAULT_RANDSEED 53 /**< initial random seed */
78 
79 #define BOUNDSWITCH 0.9999 /**< threshold for bound switching - see SCIPcalcMIR() */
80 #define POSTPROCESS TRUE /**< apply postprocessing after MIR calculation - see SCIPcalcMIR() */
81 #define USEVBDS TRUE /**< use variable bounds - 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_RANDNUMGEN* randnumgen; /**< random number generator */
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
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 && SCIPgetRowNumIntCols(scip, cut) == SCIProwGetNNonz(cut) )
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 separator */
168 
169  return SCIP_OKAY;
170 }
171 
172 /** destructor of separator to free user data (called when SCIP is exiting) */
173 /**! [SnippetSepaFreeGomory] */
174 static
175 SCIP_DECL_SEPAFREE(sepaFreeGomory)
176 { /*lint --e{715}*/
177  SCIP_SEPADATA* sepadata;
178 
179  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
180 
181  /* free separator data */
182  sepadata = SCIPsepaGetData(sepa);
183  assert(sepadata != NULL);
184 
185  SCIPfreeBlockMemory(scip, &sepadata);
186 
187  SCIPsepaSetData(sepa, NULL);
188 
189  return SCIP_OKAY;
190 }
191 /**! [SnippetSepaFreeGomory] */
192 
193 /** initialization method of separator (called after problem was transformed) */
194 static
195 SCIP_DECL_SEPAINIT(sepaInitGomory)
196 {
197  SCIP_SEPADATA* sepadata;
198 
199  sepadata = SCIPsepaGetData(sepa);
200  assert(sepadata != NULL);
201 
202  /* create and initialize random number generator */
203  SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, DEFAULT_RANDSEED) );
204 
205  return SCIP_OKAY;
206 }
207 
208 /** deinitialization method of separator (called before transformed problem is freed) */
209 static
210 SCIP_DECL_SEPAEXIT(sepaExitGomory)
211 { /*lint --e{715}*/
212  SCIP_SEPADATA* sepadata;
213 
214  sepadata = SCIPsepaGetData(sepa);
215  assert(sepadata != NULL);
216 
217  SCIPfreeRandom(scip, &sepadata->randnumgen);
218 
219  return SCIP_OKAY;
220 }
221 
222 
223 /** LP solution separation method of separator */
224 static
225 SCIP_DECL_SEPAEXECLP(sepaExeclpGomory)
226 { /*lint --e{715}*/
227  SCIP_SEPADATA* sepadata;
228  SCIP_VAR** vars;
229  SCIP_COL** cols;
230  SCIP_ROW** rows;
231  SCIP_AGGRROW* aggrrow;
232  SCIP_Real* binvrow;
233  SCIP_Real* cutcoefs;
234  SCIP_Real* basisfrac;
235  int* basisind;
236  int* basisperm;
237  int* inds;
238  int* cutinds;
239  SCIP_Real maxscale;
240  SCIP_Real minfrac;
241  SCIP_Real maxfrac;
242  SCIP_Longint maxdnom;
243  SCIP_Bool cutoff;
244  int ninds;
245  int naddedcuts;
246  int nvars;
247  int ncols;
248  int nrows;
249  int ncalls;
250  int depth;
251  int maxdepth;
252  int maxsepacuts;
253  int c;
254  int i;
255 
256  assert(sepa != NULL);
257  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
258  assert(scip != NULL);
259  assert(result != NULL);
260 
261  *result = SCIP_DIDNOTRUN;
262 
263  sepadata = SCIPsepaGetData(sepa);
264  assert(sepadata != NULL);
265 
266  depth = SCIPgetDepth(scip);
267  ncalls = SCIPsepaGetNCallsAtNode(sepa);
268 
269  minfrac = sepadata->away;
270  maxfrac = 1.0 - sepadata->away;
271 
272  /* only call separator, if we are not close to terminating */
273  if( SCIPisStopped(scip) )
274  return SCIP_OKAY;
275 
276  /* only call the gomory cut separator a given number of times at each node */
277  if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
278  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
279  return SCIP_OKAY;
280 
281  /* only call separator, if an optimal LP solution is at hand */
283  return SCIP_OKAY;
284 
285  /* only call separator, if the LP solution is basic */
286  if( !SCIPisLPSolBasic(scip) )
287  return SCIP_OKAY;
288 
289  /* only call separator, if there are fractional variables */
290  if( SCIPgetNLPBranchCands(scip) == 0 )
291  return SCIP_OKAY;
292 
293  /* get variables data */
294  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
295 
296  /* get LP data */
297  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
298  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
299  if( ncols == 0 || nrows == 0 )
300  return SCIP_OKAY;
301 
302 #if 0 /* if too many columns, separator is usually very slow: delay it until no other cuts have been found */
303  if( ncols >= 50*nrows )
304  return SCIP_OKAY;
305 
306  if( ncols >= 5*nrows )
307  {
308  int ncutsfound;
309 
310  ncutsfound = SCIPgetNCutsFound(scip);
311  if( ncutsfound > sepadata->lastncutsfound || !SCIPsepaWasLPDelayed(sepa) )
312  {
313  sepadata->lastncutsfound = ncutsfound;
314  *result = SCIP_DELAYED;
315  return SCIP_OKAY;
316  }
317  }
318 #endif
319 
320  /* set the maximal denominator in rational representation of gomory cut and the maximal scale factor to
321  * scale resulting cut to integral values to avoid numerical instabilities
322  */
323  /**@todo find better but still stable gomory cut settings: look at dcmulti, gesa3, khb0525, misc06, p2756 */
324  maxdepth = SCIPgetMaxDepth(scip);
325  if( depth == 0 )
326  {
327  maxdnom = 1000;
328  maxscale = 1000.0;
329  }
330  else if( depth <= maxdepth/4 )
331  {
332  maxdnom = 1000;
333  maxscale = 1000.0;
334  }
335  else if( depth <= maxdepth/2 )
336  {
337  maxdnom = 100;
338  maxscale = 100.0;
339  }
340  else
341  {
342  maxdnom = 10;
343  maxscale = 10.0;
344  }
345 
346  /* allocate temporary memory */
347  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
348  SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) );
349  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
350  SCIP_CALL( SCIPallocBufferArray(scip, &basisperm, nrows) );
351  SCIP_CALL( SCIPallocBufferArray(scip, &basisfrac, nrows) );
352  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
353  SCIP_CALL( SCIPallocBufferArray(scip, &inds, nrows) );
354  SCIP_CALL( SCIPaggrRowCreate(scip, &aggrrow) );
355 
356  /* get basis indices */
357  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
358 
359  for( i = 0; i < nrows; ++i )
360  {
361  SCIP_Real frac = 0.0;
362 
363  c = basisind[i];
364 
365  basisperm[i] = i;
366 
367  if( c >= 0 )
368  {
369  SCIP_VAR* var;
370 
371  assert(c < ncols);
372  var = SCIPcolGetVar(cols[c]);
374  {
375  frac = SCIPfeasFrac(scip, SCIPcolGetPrimsol(cols[c]));
376  frac = MIN(frac, 1.0 - frac);
377  }
378  }
379  else if( sepadata->separaterows )
380  {
381  SCIP_ROW* row;
382 
383  assert(0 <= -c-1 && -c-1 < nrows);
384  row = rows[-c-1];
385  if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
386  {
387  frac = SCIPfeasFrac(scip, SCIPgetRowActivity(scip, row));
388  frac = MIN(frac, 1.0 - frac);
389  }
390  }
391 
392  if( frac >= minfrac )
393  {
394  /* slightly change fractionality to have random order for equal fractions */
395  basisfrac[i] = frac + SCIPrandomGetReal(sepadata->randnumgen, -1e-6, 1e-6);
396  }
397  else
398  {
399  basisfrac[i] = 0.0;
400  }
401  }
402 
403  /* sort basis indices by fractionality */
404  SCIPsortDownRealInt(basisfrac, basisperm, nrows);
405 
406  /* get the maximal number of cuts allowed in a separation round */
407  if( depth == 0 )
408  maxsepacuts = sepadata->maxsepacutsroot;
409  else
410  maxsepacuts = sepadata->maxsepacuts;
411 
412  SCIPdebugMsg(scip, "searching gomory cuts: %d cols, %d rows, maxdnom=%" SCIP_LONGINT_FORMAT ", maxscale=%g, maxcuts=%d\n",
413  ncols, nrows, maxdnom, maxscale, maxsepacuts);
414 
415  cutoff = FALSE;
416  naddedcuts = 0;
417 
418  /* for all basic columns belonging to integer variables, try to generate a gomory cut */
419  for( i = 0; i < nrows && naddedcuts < maxsepacuts && !SCIPisStopped(scip) && !cutoff; ++i )
420  {
421  SCIP_Real cutrhs;
422  SCIP_Real cutefficacy;
423  SCIP_Bool success;
424  SCIP_Bool cutislocal;
425  int cutnnz;
426  int cutrank;
427  int j;
428 
429  if( basisfrac[i] == 0.0 )
430  break;
431 
432  j = basisperm[i];
433  c = basisind[j];
434 
435  /* get the row of B^-1 for this basic integer variable with fractional solution value */
436  ninds = -1;
437  SCIP_CALL( SCIPgetLPBInvRow(scip, j, binvrow, inds, &ninds) );
438 
439  SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, binvrow, inds, ninds,
440  sepadata->sidetypebasis, allowlocal, 2, (int) MAXAGGRLEN(nvars), &success) );
441 
442  if( !success )
443  continue;
444 
445  SCIP_CALL( SCIPcalcMIR(scip, NULL, POSTPROCESS, BOUNDSWITCH, USEVBDS, allowlocal, FIXINTEGRALRHS, NULL, NULL, minfrac, maxfrac,
446  1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
447 
448  assert(allowlocal || !cutislocal);
449 
450  /* @todo Currently we are using the SCIPcalcMIR() function to compute the coefficients of the Gomory
451  * cut. Alternatively, we could use the direct version (see thesis of Achterberg formula (8.4)) which
452  * leads to cut a of the form \sum a_i x_i \geq 1. Rumor has it that these cuts are better.
453  */
454 
455  SCIPdebugMsg(scip, " -> success=%u, rhs=%g, efficacy=%g\n", success, cutrhs, cutefficacy);
456 
457  /* if successful, convert dense cut into sparse row, and add the row as a cut */
458  if( success )
459  {
460  if( cutnnz == 0 && SCIPisFeasNegative(scip, cutrhs) )
461  {
462  SCIPdebugMsg(scip, " -> gomory cut detected infeasibility with cut 0 <= %f\n", cutrhs);
463  cutoff = TRUE;
464  }
465  else if( SCIPisEfficacious(scip, cutefficacy) )
466  {
467  /* Only take efficient cuts, except for cuts with one non-zero coefficients (= bound
468  * changes); the latter cuts will be handled internally in sepastore.
469  */
470  SCIP_ROW* cut;
471  char cutname[SCIP_MAXSTRLEN];
472  int v;
473 
474  /* construct cut name */
475  if( c >= 0 )
476  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gom%d_x%d", SCIPgetNLPs(scip), c);
477  else
478  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gom%d_s%d", SCIPgetNLPs(scip), -c-1);
479 
480  /* create empty cut */
481  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs,
482  cutislocal, FALSE, sepadata->dynamiccuts) );
483 
484  /* set cut rank */
485  SCIProwChgRank(cut, cutrank);
486 
487  /* cache the row extension and only flush them if the cut gets added */
489 
490  /* collect all non-zero coefficients */
491  for( v = 0; v < cutnnz; ++v )
492  {
493  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[v]], cutcoefs[v]) );
494  }
495 
496  if( cutnnz == 1 )
497  {
498  /* add the bound change as cut to avoid that the LP gets modified. that would mean the LP is not flushed
499  * and the method SCIPgetLPBInvRow() fails; SCIP internally will apply that bound change automatically
500  */
501  SCIP_CALL( SCIPaddRow(scip, cut, TRUE, &cutoff) );
502  naddedcuts++;
503  }
504  else
505  {
506  SCIP_Bool useful;
507 
508  assert(success == TRUE);
509  assert(SCIPisInfinity(scip, -SCIProwGetLhs(cut)));
510  assert(!SCIPisInfinity(scip, SCIProwGetRhs(cut)));
511 
512  SCIPdebugMsg(scip, " -> gomory cut for <%s>: rhs=%f, eff=%f\n",
513  c >= 0 ? SCIPvarGetName(SCIPcolGetVar(cols[c])) : SCIProwGetName(rows[-c-1]),
514  cutrhs, cutefficacy);
515 
516  SCIP_CALL( evaluateCutNumerics(scip, sepadata, cut, maxdnom, maxscale, &useful) );
517 
518  if( useful )
519  {
520  SCIPdebugMsg(scip, " -> found gomory cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
521  cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
522  SCIPgetCutEfficacy(scip, NULL, cut),
525 
526  /* flush all changes before adding the cut */
528 
529  if( SCIPisCutNew(scip, cut) )
530  {
531  /* add global cuts which are not implicit bound changes to the cut pool */
532  if( !cutislocal )
533  {
534  if( sepadata->delayedcuts )
535  {
537  }
538  else
539  {
540  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
541  }
542  }
543  else
544  {
545  /* local cuts we add to the sepastore */
546  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, &cutoff) );
547  }
548 
549  naddedcuts++;
550  }
551  }
552  }
553  /* release the row */
554  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
555  }
556  }
557  }
558 
559  /* free temporary memory */
560  SCIPfreeBufferArray(scip, &inds);
561  SCIPfreeBufferArray(scip, &binvrow);
562  SCIPfreeBufferArray(scip, &basisfrac);
563  SCIPfreeBufferArray(scip, &basisperm);
564  SCIPfreeBufferArray(scip, &basisind);
565  SCIPfreeBufferArray(scip, &cutinds);
566  SCIPfreeBufferArray(scip, &cutcoefs);
567  SCIPaggrRowFree(scip, &aggrrow);
568 
569  SCIPdebugMsg(scip, "end searching gomory cuts: found %d cuts\n", naddedcuts);
570 
571  sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
572 
573  /* evaluate the result of the separation */
574  if( cutoff )
575  *result = SCIP_CUTOFF;
576  else if ( naddedcuts > 0 )
577  *result = SCIP_SEPARATED;
578  else
579  *result = SCIP_DIDNOTFIND;
580 
581  return SCIP_OKAY;
582 }
583 
584 
585 /*
586  * separator specific interface methods
587  */
588 
589 /** creates the Gomory MIR cut separator and includes it in SCIP */
591  SCIP* scip /**< SCIP data structure */
592  )
593 {
594  SCIP_SEPADATA* sepadata;
595  SCIP_SEPA* sepa;
596 
597  /* create separator data */
598  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
599  sepadata->lastncutsfound = 0;
600 
601  /* include separator */
604  sepaExeclpGomory, NULL,
605  sepadata) );
606 
607  assert(sepa != NULL);
608 
609  /* set non-NULL pointers to callback methods */
610  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyGomory) );
611  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeGomory) );
612  SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitGomory) );
613  SCIP_CALL( SCIPsetSepaExit(scip, sepa, sepaExitGomory) );
614 
615  /* add separator parameters */
617  "separating/gomory/maxrounds",
618  "maximal number of gomory separation rounds per node (-1: unlimited)",
619  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
621  "separating/gomory/maxroundsroot",
622  "maximal number of gomory separation rounds in the root node (-1: unlimited)",
623  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
625  "separating/gomory/maxsepacuts",
626  "maximal number of gomory cuts separated per separation round",
627  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
629  "separating/gomory/maxsepacutsroot",
630  "maximal number of gomory cuts separated per separation round in the root node",
631  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
633  "separating/gomory/maxrank",
634  "maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited)",
635  &sepadata->maxrank, FALSE, DEFAULT_MAXRANK, -1, INT_MAX, NULL, NULL) );
637  "separating/gomory/maxrankintegral",
638  "maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited)",
639  &sepadata->maxrankintegral, FALSE, DEFAULT_MAXRANKINTEGRAL, -1, INT_MAX, NULL, NULL) );
641  "separating/gomory/away",
642  "minimal integrality violation of a basis variable in order to try Gomory cut",
643  &sepadata->away, FALSE, DEFAULT_AWAY, 1e-4, 0.5, NULL, NULL) );
645  "separating/gomory/dynamiccuts",
646  "should generated cuts be removed from the LP if they are no longer tight?",
647  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
649  "separating/gomory/makeintegral",
650  "try to scale cuts to integral coefficients",
651  &sepadata->makeintegral, TRUE, DEFAULT_MAKEINTEGRAL, NULL, NULL) );
653  "separating/gomory/forcecuts",
654  "if conversion to integral coefficients failed still consider the cut",
655  &sepadata->forcecuts, TRUE, DEFAULT_FORCECUTS, NULL, NULL) );
657  "separating/gomory/separaterows",
658  "separate rows with integral slack",
659  &sepadata->separaterows, TRUE, DEFAULT_SEPARATEROWS, NULL, NULL) );
661  "separating/gomory/delayedcuts",
662  "should cuts be added to the delayed cut pool?",
663  &sepadata->delayedcuts, TRUE, DEFAULT_DELAYEDCUTS, NULL, NULL) );
665  "separating/gomory/sidetypebasis",
666  "choose side types of row (lhs/rhs) based on basis information?",
667  &sepadata->sidetypebasis, TRUE, DEFAULT_SIDETYPEBASIS, NULL, NULL) );
668 
669  return SCIP_OKAY;
670 }
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip.c:48620
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_gomory.c:67
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1567
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29778
SCIP_RETCODE SCIPincludeSepaGomory(SCIP *scip)
Definition: sepa_gomory.c:590
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30607
static SCIP_RETCODE evaluateCutNumerics(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW *cut, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool *useful)
Definition: sepa_gomory.c:111
#define SEPA_PRIORITY
Definition: sepa_gomory.c:58
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30630
#define SCIP_MAXSTRLEN
Definition: def.h:259
#define SEPA_DESC
Definition: sepa_gomory.c:57
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
Definition: scip.c:48602
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30662
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16402
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_gomory.c:65
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16540
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47381
SCIP_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:35045
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip.c:43089
#define DEFAULT_DELAYEDCUTS
Definition: sepa_gomory.c:75
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16481
#define FALSE
Definition: def.h:64
#define DEFAULT_MAXROUNDS
Definition: sepa_gomory.c:64
#define SEPA_MAXBOUNDDIST
Definition: sepa_gomory.c:60
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
#define TRUE
Definition: def.h:63
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:646
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_DECL_SEPAEXIT(sepaExitGomory)
Definition: sepa_gomory.c:210
#define DEFAULT_MAKEINTEGRAL
Definition: sepa_gomory.c:72
#define FIXINTEGRALRHS
Definition: sepa_gomory.c:82
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:47453
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip.c:29556
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:37028
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip.c:7427
#define SCIPdebugMsg
Definition: scip.h:455
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
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:46409
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30883
#define USEVBDS
Definition: sepa_gomory.c:81
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:557
#define DEFAULT_MAXRANKINTEGRAL
Definition: sepa_gomory.c:69
static SCIP_DECL_SEPAEXECLP(sepaExeclpGomory)
Definition: sepa_gomory.c:225
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29731
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16205
#define MAKECONTINTEGRAL
Definition: sepa_gomory.c:83
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30865
#define DEFAULT_MAXSEPACUTS
Definition: sepa_gomory.c:66
#define SEPA_USESSUBSCIP
Definition: sepa_gomory.c:61
int SCIPgetNCutsFound(SCIP *scip)
Definition: scip.c:42896
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
Definition: scip.c:7475
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:773
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip.c:34540
#define DEFAULT_MAXRANK
Definition: sepa_gomory.c:68
#define DEFAULT_FORCECUTS
Definition: sepa_gomory.c:73
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:16580
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:567
#define DEFAULT_SEPARATEROWS
Definition: sepa_gomory.c:74
#define DEFAULT_SIDETYPEBASIS
Definition: sepa_gomory.c:76
static SCIP_DECL_SEPAINIT(sepaInitGomory)
Definition: sepa_gomory.c:195
#define SEPA_DELAY
Definition: sepa_gomory.c:62
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16491
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30954
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:34655
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:16600
#define DEFAULT_DYNAMICCUTS
Definition: sepa_gomory.c:70
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
SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
Definition: sepa.c:883
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition: cuts.c:3634
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
#define SEPA_NAME
Definition: sepa_gomory.c:56
int SCIPgetRowNumIntCols(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30847
#define SEPA_FREQ
Definition: sepa_gomory.c:59
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:34766
public methods for LP management
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
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:34499
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip.c:29750
Gomory MIR Cuts.
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:34748
#define MAXAGGRLEN(nvars)
Definition: sepa_gomory.c:85
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9388
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:16570
static SCIP_DECL_SEPACOPY(sepaCopyGomory)
Definition: sepa_gomory.c:160
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30534
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip.c:7443
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: scip.c:7459
SCIP_RETCODE SCIPaggrRowSumRows(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid)
Definition: cuts.c:2087
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16251
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:16703
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
#define POSTPROCESS
Definition: sepa_gomory.c:80
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1535
#define SCIP_Longint
Definition: def.h:134
#define DEFAULT_AWAY
Definition: sepa_gomory.c:71
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
#define BOUNDSWITCH
Definition: sepa_gomory.c:79
#define DEFAULT_RANDSEED
Definition: sepa_gomory.c:77
static SCIP_DECL_SEPAFREE(sepaFreeGomory)
Definition: sepa_gomory.c:175
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:46423
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29634
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:42308
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
Definition: scip.c:30805
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:16457
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
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:38
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
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:31065