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