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