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 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 #define DEFAULT_RANDSEED 53 /**< initial random seed */
79 
80 #define BOUNDSWITCH 0.9999 /**< threshold for bound switching - see SCIPcalcMIR() */
81 #define USEVBDS TRUE /**< use variable bounds - see SCIPcalcMIR() */
82 #define ALLOWLOCAL TRUE /**< allow to generate local cuts - see SCIPcalcMIR() */
83 #define FIXINTEGRALRHS FALSE /**< try to generate an integral rhs - see SCIPcalcMIR() */
84 #define MAKECONTINTEGRAL FALSE /**< convert continuous variable to integral variables in SCIPmakeRowIntegral() */
85 
86 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) /**< maximal length of base inequality */
87 
88 
89 /** separator data */
90 struct SCIP_SepaData
91 {
92  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
93  SCIP_Real maxweightrange; /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
94  SCIP_Real away; /**< minimal integrality violation of a basis variable in order to try Gomory cut */
95  int maxrounds; /**< maximal number of gomory separation rounds per node (-1: unlimited) */
96  int maxroundsroot; /**< maximal number of gomory separation rounds in the root node (-1: unlimited) */
97  int maxsepacuts; /**< maximal number of gomory cuts separated per separation round */
98  int maxsepacutsroot; /**< maximal number of gomory cuts separated per separation round in root node */
99  int maxrank; /**< maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited) */
100  int maxrankintegral; /**< maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited) */
101  int lastncutsfound; /**< total number of cuts found after last call of separator */
102  SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
103  SCIP_Bool makeintegral; /**< try to scale all cuts to integral coefficients */
104  SCIP_Bool forcecuts; /**< if conversion to integral coefficients failed still consider the cut */
105  SCIP_Bool separaterows; /**< separate rows with integral slack */
106  SCIP_Bool delayedcuts; /**< should cuts be added to the delayed cut pool? */
107  SCIP_Bool sidetypebasis; /**< choose side types of row (lhs/rhs) based on basis information? */
108 };
109 
110 
111 /** returns TRUE if the cut can be taken, otherwise FALSE if there some numerical evidences */
112 static
114  SCIP* scip, /**< SCIP data structure */
115  SCIP_SEPADATA* sepadata, /**< data of the separator */
116  SCIP_ROW* cut, /**< cut to check */
117  SCIP_Longint maxdnom, /**< maximal denominator to use for scaling */
118  SCIP_Real maxscale, /**< maximal scaling factor */
119  SCIP_Bool* useful /**< pointer to store if the cut is useful */
120  )
121 {
122  SCIP_Bool madeintegral;
123 
124  madeintegral = FALSE;
125  (*useful) = FALSE;
126 
127  if( sepadata->makeintegral )
128  {
129  /* try to scale the cut to integral values */
130  SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
131  maxdnom, maxscale, MAKECONTINTEGRAL, &madeintegral) );
132 
133  if( !madeintegral && !sepadata->forcecuts )
134  return SCIP_OKAY;
135 
136  /* in case the right hand side is plus infinity (due to scaling) the cut is useless so we are not taking it at all
137  */
138  if( madeintegral && SCIPisInfinity(scip, SCIProwGetRhs(cut)) )
139  return SCIP_OKAY;
140  }
141 
142  /* discard integral cut if the rank is too high */
143  if( madeintegral && sepadata->maxrankintegral != -1 && (SCIProwGetRank(cut) > sepadata->maxrankintegral) )
144  return SCIP_OKAY;
145 
146  /* discard cut if the rank is too high */
147  if( !madeintegral && (sepadata->maxrank != -1) && (SCIProwGetRank(cut) > sepadata->maxrank) )
148  return SCIP_OKAY;
149 
150  (*useful) = TRUE;
151 
152  return SCIP_OKAY;
153 }
154 
155 
156 /*
157  * Callback methods
158  */
159 
160 /** copy method for separator plugins (called when SCIP copies plugins) */
161 static
162 SCIP_DECL_SEPACOPY(sepaCopyGomory)
163 { /*lint --e{715}*/
164  assert(scip != NULL);
165  assert(sepa != NULL);
166  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
167 
168  /* call inclusion method of constraint handler */
170 
171  return SCIP_OKAY;
172 }
173 
174 /** destructor of separator to free user data (called when SCIP is exiting) */
175 /**! [SnippetSepaFreeGomory] */
176 static
177 SCIP_DECL_SEPAFREE(sepaFreeGomory)
178 { /*lint --e{715}*/
179  SCIP_SEPADATA* sepadata;
180 
181  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
182 
183  /* free separator data */
184  sepadata = SCIPsepaGetData(sepa);
185  assert(sepadata != NULL);
186 
187  /* free random number generator */
188  SCIPrandomFree(&sepadata->randnumgen);
189 
190  SCIPfreeBlockMemory(scip, &sepadata);
191 
192  SCIPsepaSetData(sepa, NULL);
193 
194  return SCIP_OKAY;
195 }
196 /**! [SnippetSepaFreeGomory] */
197 
198 
199 /** LP solution separation method of separator */
200 static
201 SCIP_DECL_SEPAEXECLP(sepaExeclpGomory)
202 { /*lint --e{715}*/
203  SCIP_SEPADATA* sepadata;
204  SCIP_VAR** vars;
205  SCIP_COL** cols;
206  SCIP_ROW** rows;
207  SCIP_Real* binvrow;
208  SCIP_Real* cutcoefs;
209  SCIP_Real maxscale;
210  SCIP_Real minfrac;
211  SCIP_Real maxfrac;
212  SCIP_Longint maxdnom;
213  SCIP_Bool cutoff;
214  int* sidetypes = NULL;
215  int* basisind;
216  int* inds;
217  int ninds;
218  int naddedcuts;
219  int nvars;
220  int ncols;
221  int nrows;
222  int ncalls;
223  int depth;
224  int maxdepth;
225  int maxsepacuts;
226  int c;
227  int i;
228 
229  assert(sepa != NULL);
230  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
231  assert(scip != NULL);
232  assert(result != NULL);
233 
234  *result = SCIP_DIDNOTRUN;
235 
236  sepadata = SCIPsepaGetData(sepa);
237  assert(sepadata != NULL);
238 
239  depth = SCIPgetDepth(scip);
240  ncalls = SCIPsepaGetNCallsAtNode(sepa);
241 
242  minfrac = sepadata->away;
243  maxfrac = 1.0 - sepadata->away;
244 
245  /* only call separator, if we are not close to terminating */
246  if( SCIPisStopped(scip) )
247  return SCIP_OKAY;
248 
249  /* only call the gomory cut separator a given number of times at each node */
250  if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
251  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
252  return SCIP_OKAY;
253 
254  /* only call separator, if an optimal LP solution is at hand */
256  return SCIP_OKAY;
257 
258  /* only call separator, if the LP solution is basic */
259  if( !SCIPisLPSolBasic(scip) )
260  return SCIP_OKAY;
261 
262  /* only call separator, if there are fractional variables */
263  if( SCIPgetNLPBranchCands(scip) == 0 )
264  return SCIP_OKAY;
265 
266  /* get variables data */
267  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
268 
269  /* get LP data */
270  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
271  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
272  if( ncols == 0 || nrows == 0 )
273  return SCIP_OKAY;
274 
275 #if 0 /* if too many columns, separator is usually very slow: delay it until no other cuts have been found */
276  if( ncols >= 50*nrows )
277  return SCIP_OKAY;
278 
279  if( ncols >= 5*nrows )
280  {
281  int ncutsfound;
282 
283  ncutsfound = SCIPgetNCutsFound(scip);
284  if( ncutsfound > sepadata->lastncutsfound || !SCIPsepaWasLPDelayed(sepa) )
285  {
286  sepadata->lastncutsfound = ncutsfound;
287  *result = SCIP_DELAYED;
288  return SCIP_OKAY;
289  }
290  }
291 #endif
292 
293  /* set the maximal denominator in rational representation of gomory cut and the maximal scale factor to
294  * scale resulting cut to integral values to avoid numerical instabilities
295  */
296  /**@todo find better but still stable gomory cut settings: look at dcmulti, gesa3, khb0525, misc06, p2756 */
297  maxdepth = SCIPgetMaxDepth(scip);
298  if( depth == 0 )
299  {
300  maxdnom = 1000;
301  maxscale = 1000.0;
302  }
303  else if( depth <= maxdepth/4 )
304  {
305  maxdnom = 1000;
306  maxscale = 1000.0;
307  }
308  else if( depth <= maxdepth/2 )
309  {
310  maxdnom = 100;
311  maxscale = 100.0;
312  }
313  else
314  {
315  maxdnom = 10;
316  maxscale = 10.0;
317  }
318 
319  /* allocate temporary memory */
320  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
321  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
322  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
323  SCIP_CALL( SCIPallocBufferArray(scip, &inds, nrows) );
324  if ( sepadata->sidetypebasis )
325  {
326  SCIP_CALL( SCIPallocBufferArray(scip, &sidetypes, nrows) );
327  }
328 
329  /* get basis indices */
330  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
331 
332  /* permute basis indices to reduce performance variability */
333  SCIPrandomPermuteIntArray(sepadata->randnumgen, basisind, 0, nrows);
334 
335  /* get the maximal number of cuts allowed in a separation round */
336  if( depth == 0 )
337  maxsepacuts = sepadata->maxsepacutsroot;
338  else
339  maxsepacuts = sepadata->maxsepacuts;
340 
341  SCIPdebugMsg(scip, "searching gomory cuts: %d cols, %d rows, maxdnom=%" SCIP_LONGINT_FORMAT ", maxscale=%g, maxcuts=%d\n",
342  ncols, nrows, maxdnom, maxscale, maxsepacuts);
343 
344  cutoff = FALSE;
345  naddedcuts = 0;
346 
347  /* for all basic columns belonging to integer variables, try to generate a gomory cut */
348  for( i = 0; i < nrows && naddedcuts < maxsepacuts && !SCIPisStopped(scip) && !cutoff; ++i )
349  {
350  SCIP_Bool tryrow;
351 
352  tryrow = FALSE;
353  c = basisind[i];
354  if( c >= 0 )
355  {
356  SCIP_VAR* var;
357 
358  assert(c < ncols);
359  var = SCIPcolGetVar(cols[c]);
361  {
362  SCIP_Real primsol;
363 
364  primsol = SCIPcolGetPrimsol(cols[c]);
365  assert(SCIPgetVarSol(scip, var) == primsol); /*lint !e777*/
366 
367  if( SCIPfeasFrac(scip, primsol) >= minfrac )
368  {
369  SCIPdebugMsg(scip, "trying gomory cut for col <%s> [%g]\n", SCIPvarGetName(var), primsol);
370  tryrow = TRUE;
371  }
372  }
373  }
374  else if( sepadata->separaterows )
375  {
376  SCIP_ROW* row;
377 
378  assert(0 <= -c-1 && -c-1 < nrows);
379  row = rows[-c-1];
380  if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
381  {
382  SCIP_Real primsol;
383 
384  primsol = SCIPgetRowActivity(scip, row);
385  if( SCIPfeasFrac(scip, primsol) >= minfrac )
386  {
387  SCIPdebugMsg(scip, "trying gomory cut for row <%s> [%g]\n", SCIProwGetName(row), primsol);
388  tryrow = TRUE;
389  }
390  }
391  }
392 
393  if( tryrow )
394  {
395  SCIP_Real cutrhs;
396  SCIP_Real cutact;
397  SCIP_Bool success;
398  SCIP_Bool cutislocal;
399  int cutrank;
400 
401  /* get the row of B^-1 for this basic integer variable with fractional solution value */
402  ninds = -1;
403  SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow, inds, &ninds) );
404 
405  if ( sepadata->sidetypebasis )
406  {
407  int k;
408 
409  assert( sidetypes != NULL );
410  for (k = 0; k < nrows; ++k)
411  {
412  SCIP_BASESTAT stat;
413  SCIP_ROW* row;
414 
415  row = rows[k];
416  assert( row != NULL );
417 
418  /* for equations take automatic choice */
419  if ( SCIPisEQ(scip, SCIProwGetLhs(row), SCIProwGetRhs(row)) )
420  sidetypes[k] = 0;
421  else
422  {
423  /* for ranged rows use basis status */
424  assert( SCIPisLPSolBasic(scip) );
425  stat = SCIProwGetBasisStatus(row);
426  if ( stat == SCIP_BASESTAT_LOWER )
427  {
428  assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
429  sidetypes[k] = -1;
430  }
431  else if ( stat == SCIP_BASESTAT_UPPER )
432  {
433  assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) );
434  sidetypes[k] = 1;
435  }
436  else
437  sidetypes[k] = 0;
438  }
439  }
440  }
441 
442  cutact = 0.0;
443  cutrhs = SCIPinfinity(scip);
444 
445  /* need to ensure that is sparsity information is requested from SCIPgetLPBInvRow
446  * that it is used in SCIPcalcMIR */
447  if( inds != NULL && ninds > -1 )
448  {
449  /* create a MIR cut out of the weighted LP rows using the B^-1 row as weights */
451  (int) MAXAGGRLEN(nvars), sepadata->maxweightrange, minfrac, maxfrac, binvrow, -1.0, inds, ninds, -1,
452  sidetypes, 1.0, NULL, NULL, cutcoefs, &cutrhs, &cutact, &success, &cutislocal, &cutrank) );
453  }
454  else
455  {
456  /* create a MIR cut out of the weighted LP rows using the B^-1 row as weights */
458  (int) MAXAGGRLEN(nvars), sepadata->maxweightrange, minfrac, maxfrac, binvrow, -1.0, NULL, -1, -1,
459  sidetypes, 1.0, NULL, NULL, cutcoefs, &cutrhs, &cutact, &success, &cutislocal, &cutrank) );
460  }
461  assert(ALLOWLOCAL || !cutislocal);
462 
463  /* @todo Currently we are using the SCIPcalcMIR() function to compute the coefficients of the Gomory
464  * cut. Alternatively, we could use the direct version (see thesis of Achterberg formula (8.4)) which
465  * leads to cut a of the form \sum a_i x_i \geq 1. Rumor has it that these cuts are better.
466  */
467 
468  SCIPdebugMsg(scip, " -> success=%u: %g <= %g\n", success, cutact, cutrhs);
469 
470  /* if successful, convert dense cut into sparse row, and add the row as a cut */
471  if( success && SCIPisFeasGT(scip, cutact, cutrhs) )
472  {
473  SCIP_ROW* cut;
474  char cutname[SCIP_MAXSTRLEN];
475  int v;
476 
477  /* construct cut name */
478  if( c >= 0 )
479  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gom%d_x%d", SCIPgetNLPs(scip), c);
480  else
481  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "gom%d_s%d", SCIPgetNLPs(scip), -c-1);
482 
483  /* create empty cut */
484  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs,
485  cutislocal, FALSE, sepadata->dynamiccuts) );
486 
487  /* set cut rank */
488  SCIProwChgRank(cut, cutrank);
489 
490  /* cache the row extension and only flush them if the cut gets added */
492 
493  /* collect all non-zero coefficients */
494  for( v = 0; v < nvars; ++v )
495  {
496  if( !SCIPisZero(scip, cutcoefs[v]) )
497  {
498  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[v], cutcoefs[v]) );
499  }
500  }
501 
502  if( SCIProwGetNNonz(cut) == 0 )
503  {
504  assert(SCIPisFeasNegative(scip, cutrhs));
505  SCIPdebugMsg(scip, " -> gomory cut detected infeasibility with cut 0 <= %f\n", cutrhs);
506  cutoff = TRUE;
507  }
508  else if( SCIProwGetNNonz(cut) == 1 )
509  {
510  /* add the bound change as cut to avoid that the LP gets modified. that would mean the LP is not flushed
511  * and the method SCIPgetLPBInvRow() fails; SCIP internally will apply that bound change automatically
512  */
513  SCIP_CALL( SCIPaddCut(scip, NULL, cut, TRUE, &cutoff) );
514  naddedcuts++;
515  }
516  else
517  {
518  /* Only take efficacious cuts, except for cuts with one non-zero coefficients (= bound
519  * changes); the latter cuts will be handeled internally in sepastore.
520  */
521  if( SCIPisCutEfficacious(scip, NULL, cut) )
522  {
523  SCIP_Bool useful;
524 
525  assert(success == TRUE);
526  assert(SCIPisInfinity(scip, -SCIProwGetLhs(cut)));
527  assert(!SCIPisInfinity(scip, SCIProwGetRhs(cut)));
528 
529  SCIPdebugMsg(scip, " -> gomory cut for <%s>: act=%f, rhs=%f, eff=%f\n",
530  c >= 0 ? SCIPvarGetName(SCIPcolGetVar(cols[c])) : SCIProwGetName(rows[-c-1]),
531  cutact, cutrhs, SCIPgetCutEfficacy(scip, NULL, cut));
532 
533  SCIP_CALL( evaluateCutNumerics(scip, sepadata, cut, maxdnom, maxscale, &useful) );
534 
535  if( useful )
536  {
537  SCIPdebugMsg(scip, " -> found gomory cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
538  cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
542 
543  /* flush all changes before adding the cut */
545 
546  /* add global cuts which are not implicit bound changes to the cut pool */
547  if( !cutislocal )
548  {
549  if( sepadata->delayedcuts )
550  {
552  }
553  else
554  {
555  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
556  }
557  }
558  else
559  {
560  /* local cuts we add to the sepastore */
561  SCIP_CALL( SCIPaddCut(scip, NULL, cut, FALSE, &cutoff) );
562  }
563 
564  naddedcuts++;
565  }
566  }
567  }
568 
569  /* release the row */
570  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
571  }
572  }
573  }
574 
575  /* free temporary memory */
576  if ( sepadata->sidetypebasis )
577  {
578  SCIPfreeBufferArray(scip, &sidetypes);
579  }
580  SCIPfreeBufferArray(scip, &inds);
581  SCIPfreeBufferArray(scip, &binvrow);
582  SCIPfreeBufferArray(scip, &basisind);
583  SCIPfreeBufferArray(scip, &cutcoefs);
584 
585  SCIPdebugMsg(scip, "end searching gomory cuts: found %d cuts\n", naddedcuts);
586 
587  sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
588 
589  /* evalute the result of the separation */
590  if( cutoff )
591  *result = SCIP_CUTOFF;
592  else if ( naddedcuts > 0 )
593  *result = SCIP_SEPARATED;
594  else
595  *result = SCIP_DIDNOTFIND;
596 
597  return SCIP_OKAY;
598 }
599 
600 
601 /*
602  * separator specific interface methods
603  */
604 
605 /** creates the Gomory MIR cut separator and includes it in SCIP */
607  SCIP* scip /**< SCIP data structure */
608  )
609 {
610  SCIP_SEPADATA* sepadata;
611  SCIP_SEPA* sepa;
612 
613  /* create separator data */
614  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
615  sepadata->lastncutsfound = 0;
616 
617  /* create random number generator */
618  SCIP_CALL( SCIPrandomCreate(&sepadata->randnumgen, SCIPblkmem(scip),
620 
621  /* include separator */
624  sepaExeclpGomory, NULL,
625  sepadata) );
626 
627  assert(sepa != NULL);
628 
629  /* set non-NULL pointers to callback methods */
630  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyGomory) );
631  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeGomory) );
632 
633  /* add separator parameters */
635  "separating/gomory/maxrounds",
636  "maximal number of gomory separation rounds per node (-1: unlimited)",
637  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
639  "separating/gomory/maxroundsroot",
640  "maximal number of gomory separation rounds in the root node (-1: unlimited)",
641  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
643  "separating/gomory/maxsepacuts",
644  "maximal number of gomory cuts separated per separation round",
645  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
647  "separating/gomory/maxsepacutsroot",
648  "maximal number of gomory cuts separated per separation round in the root node",
649  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
651  "separating/gomory/maxrank",
652  "maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited)",
653  &sepadata->maxrank, FALSE, DEFAULT_MAXRANK, -1, INT_MAX, NULL, NULL) );
655  "separating/gomory/maxrankintegral",
656  "maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited)",
657  &sepadata->maxrankintegral, FALSE, DEFAULT_MAXRANKINTEGRAL, -1, INT_MAX, NULL, NULL) );
659  "separating/gomory/away",
660  "minimal integrality violation of a basis variable in order to try Gomory cut",
661  &sepadata->away, FALSE, DEFAULT_AWAY, 1e-4, 0.5, NULL, NULL) );
663  "separating/gomory/maxweightrange",
664  "maximal valid range max(|weights|)/min(|weights|) of row weights",
665  &sepadata->maxweightrange, TRUE, DEFAULT_MAXWEIGHTRANGE, 1.0, SCIP_REAL_MAX, NULL, NULL) );
667  "separating/gomory/dynamiccuts",
668  "should generated cuts be removed from the LP if they are no longer tight?",
669  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
671  "separating/gomory/makeintegral",
672  "try to scale cuts to integral coefficients",
673  &sepadata->makeintegral, TRUE, DEFAULT_MAKEINTEGRAL, NULL, NULL) );
675  "separating/gomory/forcecuts",
676  "if conversion to integral coefficients failed still consider the cut",
677  &sepadata->forcecuts, TRUE, DEFAULT_FORCECUTS, NULL, NULL) );
679  "separating/gomory/separaterows",
680  "separate rows with integral slack",
681  &sepadata->separaterows, TRUE, DEFAULT_SEPARATEROWS, NULL, NULL) );
683  "separating/gomory/delayedcuts",
684  "should cuts be added to the delayed cut pool?",
685  &sepadata->delayedcuts, TRUE, DEFAULT_DELAYEDCUTS, NULL, NULL) );
687  "separating/gomory/sidetypebasis",
688  "choose side types of row (lhs/rhs) based on basis information?",
689  &sepadata->sidetypebasis, TRUE, DEFAULT_SIDETYPEBASIS, NULL, NULL) );
690 
691  return SCIP_OKAY;
692 }
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_gomory.c:67
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29309
SCIP_RETCODE SCIPincludeSepaGomory(SCIP *scip)
Definition: sepa_gomory.c:606
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30233
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:113
#define SEPA_PRIORITY
Definition: sepa_gomory.c:58
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30256
enum SCIP_BaseStat SCIP_BASESTAT
Definition: type_lpi.h:86
#define SCIP_MAXSTRLEN
Definition: def.h:215
#define SEPA_DESC
Definition: sepa_gomory.c:57
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30288
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16232
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_gomory.c:65
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16370
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:46175
SCIP_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:34243
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip.c:42144
#define DEFAULT_DELAYEDCUTS
Definition: sepa_gomory.c:76
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11505
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16311
#define FALSE
Definition: def.h:64
#define DEFAULT_MAXROUNDS
Definition: sepa_gomory.c:64
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:16359
#define SEPA_MAXBOUNDDIST
Definition: sepa_gomory.c:60
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
#define TRUE
Definition: def.h:63
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:632
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define DEFAULT_MAKEINTEGRAL
Definition: sepa_gomory.c:73
#define FIXINTEGRALRHS
Definition: sepa_gomory.c:83
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, SCIP_Real maxweight, int *weightinds, int nweightinds, int rowlensum, int *sidetypes, SCIP_Real scale, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
Definition: scip.c:29473
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
#define ALLOWLOCAL
Definition: sepa_gomory.c:82
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:46247
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip.c:29087
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:36161
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip.c:7367
#define SCIPdebugMsg
Definition: scip.h:451
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:4202
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:45246
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30491
#define USEVBDS
Definition: sepa_gomory.c:81
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:543
#define DEFAULT_MAXRANKINTEGRAL
Definition: sepa_gomory.c:69
static SCIP_DECL_SEPAEXECLP(sepaExeclpGomory)
Definition: sepa_gomory.c:201
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29262
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:33761
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16035
#define MAKECONTINTEGRAL
Definition: sepa_gomory.c:84
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30473
#define DEFAULT_MAXSEPACUTS
Definition: sepa_gomory.c:66
#define SEPA_USESSUBSCIP
Definition: sepa_gomory.c:61
int SCIPgetNCutsFound(SCIP *scip)
Definition: scip.c:41951
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:759
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
#define DEFAULT_MAXRANK
Definition: sepa_gomory.c:68
#define DEFAULT_FORCECUTS
Definition: sepa_gomory.c:74
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:16410
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:553
#define DEFAULT_SEPARATEROWS
Definition: sepa_gomory.c:75
#define NULL
Definition: lpi_spx1.cpp:137
#define DEFAULT_SIDETYPEBASIS
Definition: sepa_gomory.c:77
#define SEPA_DELAY
Definition: sepa_gomory.c:62
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46125
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16321
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30562
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:33869
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:16430
#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:7325
SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
Definition: sepa.c:869
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
#define SEPA_NAME
Definition: sepa_gomory.c:56
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:8764
#define SEPA_FREQ
Definition: sepa_gomory.c:59
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:33964
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:30051
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25467
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:33738
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip.c:29281
Gomory MIR Cuts.
#define DEFAULT_MAXWEIGHTRANGE
Definition: sepa_gomory.c:71
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
#define MAXAGGRLEN(nvars)
Definition: sepa_gomory.c:86
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:16400
#define SCIP_REAL_MAX
Definition: def.h:136
static SCIP_DECL_SEPACOPY(sepaCopyGomory)
Definition: sepa_gomory.c:162
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30160
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip.c:7383
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16081
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:16533
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define SCIP_Longint
Definition: def.h:120
#define DEFAULT_AWAY
Definition: sepa_gomory.c:72
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
#define BOUNDSWITCH
Definition: sepa_gomory.c:80
#define DEFAULT_RANDSEED
Definition: sepa_gomory.c:78
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:19446
static SCIP_DECL_SEPAFREE(sepaFreeGomory)
Definition: sepa_gomory.c:177
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45260
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29165
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:41363
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:30431
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:16287
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:4258
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:4176
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30673