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