SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2025 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
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"
78#include "scip/scip_sepa.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 */
120struct 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 */
145static
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 */
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 */
190static
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 */
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 */
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. */
281 ++(*naddedcuts);
282 }
283 else
284 {
285 SCIP_Bool useful;
286
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),
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 {
310 }
311 else
312 {
314 }
315 }
316 else
317 {
318 /* local cuts we add to the sepastore */
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) */
338static
339SCIP_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] */
353static
354SCIP_DECL_SEPAFREE(sepaFreeGomory)
355{ /*lint --e{715}*/
357
358 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
359
360 /* free separator data */
362 assert(sepadata != NULL);
363
365
366 SCIPsepaSetData(sepa, NULL);
367
368 return SCIP_OKAY;
369}
370/**! [SnippetSepaFreeGomory] */
371
372/** initialization method of separator (called after problem was transformed) */
373static
374SCIP_DECL_SEPAINIT(sepaInitGomory)
375{
377
379 assert(sepadata != NULL);
380
381 /* create and initialize random number generator */
383
384 return SCIP_OKAY;
385}
386
387/** deinitialization method of separator (called before transformed problem is freed) */
388static
389SCIP_DECL_SEPAEXIT(sepaExitGomory)
390{ /*lint --e{715}*/
392
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 */
403static
404SCIP_DECL_SEPAEXECLP(sepaExeclpGomory)
405{ /*lint --e{715}*/
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;
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
447
449 assert(sepadata != NULL);
450
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 */
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 */
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 */
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 assert(c < ncols);
558 var = SCIPcolGetVar(cols[c]);
560 {
562 frac = MIN(frac, 1.0 - frac);
563 }
564 }
565 else if( sepadata->separaterows )
566 {
567 SCIP_ROW* row;
568
569 assert(0 <= -c-1 && -c-1 < nrows);
570 row = rows[-c-1];
571 if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
572 {
574 frac = MIN(frac, 1.0 - frac);
575 }
576 }
577
578 if( frac >= minfrac )
579 {
580 /* slightly change fractionality to have random order for equal fractions */
581 basisfrac[i] = frac + SCIPrandomGetReal(sepadata->randnumgen, -1e-6, 1e-6);
582 }
583 else
584 {
585 basisfrac[i] = 0.0;
586 }
587 }
588
589 /* sort basis indices by fractionality */
590 SCIPsortDownRealInt(basisfrac, basisperm, nrows);
591
592 /* get the maximal number of cuts allowed in a separation round */
593 if( depth == 0 )
594 maxsepacuts = sepadata->maxsepacutsroot;
595 else
596 maxsepacuts = sepadata->maxsepacuts;
597
598 SCIPdebugMsg(scip, "searching gomory cuts: %d cols, %d rows, maxdnom=%" SCIP_LONGINT_FORMAT ", maxscale=%g, maxcuts=%d\n",
599 ncols, nrows, maxdnom, maxscale, maxsepacuts);
600
601 cutoff = FALSE;
602 naddedcuts = 0;
603
604 /* for all basic columns belonging to integer variables, try to generate a gomory cut */
605 for( i = 0; i < nrows && naddedcuts < maxsepacuts && !SCIPisStopped(scip) && !cutoff; ++i )
606 {
607 SCIP_Real cutrhs;
608 SCIP_Real cutefficacy = 0.0;
609 SCIP_Bool success;
610 SCIP_Bool cutislocal;
611 SCIP_Bool strongcgsuccess = FALSE;
612 int ninds = -1;
613 int cutnnz;
614 int cutrank;
615
616 if( basisfrac[i] == 0.0 )
617 break;
618
619 j = basisperm[i];
620 c = basisind[j];
621
622 /* get the row of B^-1 for this basic integer variable with fractional solution value */
623 SCIP_CALL( SCIPgetLPBInvRow(scip, j, binvrow, inds, &ninds) );
624
625 SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, binvrow, inds, ninds,
626 sepadata->sidetypebasis, allowlocal, 2, (int) MAXAGGRLEN(nvars), &success) );
627
628 if( !success )
629 continue;
630
631 /* try to create a strong CG cut out of the aggregation row */
632 if( separatescg )
633 {
634 SCIP_CALL( SCIPcalcStrongCG(scip, NULL, POSTPROCESS, BOUNDSWITCH, USEVBDS, allowlocal, minfrac, maxfrac,
635 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &strongcgsuccess) );
636
637 /* if we want to generate both cuts, add cut and reset cutefficacy and strongcgsuccess */
638 if( strongcgsuccess && sepadata->genbothgomscg )
639 {
640 assert(allowlocal || !cutislocal); /*lint !e644*/
641 SCIP_CALL( addCut(scip, sepadata, vars, c, maxdnom, maxscale, cutnnz, cutinds, cutcoefs, cutefficacy, cutrhs,
642 cutislocal, cutrank, TRUE, &cutoff, &naddedcuts) );
643 if( c >= 0 )
644 {
645 cutefficacies[i] = cutefficacy;
646 colindsproducedcut[i] = c;
647 }
648 cutefficacy = 0.0;
649 strongcgsuccess = FALSE;
650 if( cutoff )
651 break;
652 }
653 }
654
655 /* @todo Currently we are using the SCIPcalcMIR() function to compute the coefficients of the Gomory
656 * cut. Alternatively, we could use the direct version (see thesis of Achterberg formula (8.4)) which
657 * leads to cut a of the form \sum a_i x_i \geq 1. Rumor has it that these cuts are better.
658 */
659
660 /* try to create Gomory cut out of the aggregation row */
661 if( separategmi )
662 {
663 /* SCIPcalcMIR will only override the cut if its efficacy is larger than the one of the strongcg cut */
665 minfrac, maxfrac, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
666
667 if( success || strongcgsuccess )
668 {
669 assert(allowlocal || !cutislocal); /*lint !e644*/
670 if( success )
671 strongcgsuccess = FALSE; /* Set strongcgsuccess to FALSE, since the MIR cut has overriden the strongcg cut. */
672
673 SCIP_CALL( addCut(scip, sepadata, vars, c, maxdnom, maxscale, cutnnz, cutinds, cutcoefs, cutefficacy, cutrhs,
674 cutislocal, cutrank, strongcgsuccess, &cutoff, &naddedcuts) );
675 if( c >= 0 )
676 {
677 cutefficacies[i] = cutefficacy;
678 colindsproducedcut[i] = c;
679 }
680 }
681 }
682 }
683
684 /* Add normalized efficacy GMI statistics to history */
685 maxcutefficacy = 0.0;
686 for( i = 0; i < nrows; ++i )
687 {
688 if( cutefficacies[i] > maxcutefficacy && colindsproducedcut[i] >= 0 )
689 {
690 maxcutefficacy = cutefficacies[i];
691 }
692 }
693
694 for( i = 0; i < nrows; ++i )
695 {
696 if( colindsproducedcut[i] >= 0 && SCIPisEfficacious(scip, cutefficacies[i]) )
697 {
698 assert( maxcutefficacy > 0.0 );
699 var = SCIPcolGetVar(cols[colindsproducedcut[i]]);
700 SCIP_CALL( SCIPsetVarLastGMIScore(scip, var, cutefficacies[i] / maxcutefficacy) );
701 SCIP_CALL( SCIPincVarGMISumScore(scip, var, cutefficacies[i] / maxcutefficacy) );
702 }
703 }
704
705 /* free temporary memory */
706 SCIPaggrRowFree(scip, &aggrrow);
707 SCIPfreeBufferArray(scip, &colindsproducedcut);
708 SCIPfreeBufferArray(scip, &cutefficacies);
710 SCIPfreeBufferArray(scip, &binvrow);
711 SCIPfreeBufferArray(scip, &basisfrac);
712 SCIPfreeBufferArray(scip, &basisperm);
713 SCIPfreeBufferArray(scip, &basisind);
714 SCIPfreeBufferArray(scip, &cutinds);
715 SCIPfreeBufferArray(scip, &cutcoefs);
716
717 SCIPdebugMsg(scip, "end searching gomory cuts: found %d cuts\n", naddedcuts);
718
719 sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
720
721 /* evaluate the result of the separation */
722 if( cutoff )
724 else if ( naddedcuts > 0 )
726 else
728
729 return SCIP_OKAY;
730}
731
732
733/*
734 * separator specific interface methods
735 */
736
737/** LP solution separation method of dummy separator */
738static
739SCIP_DECL_SEPAEXECLP(sepaExeclpDummy)
740{ /*lint --e{715}*/
741 assert( result != NULL );
742
744
745 return SCIP_OKAY;
746}
747
748/** arbitrary primal solution separation method of dummy separator */
749static
750SCIP_DECL_SEPAEXECSOL(sepaExecsolDummy)
751{ /*lint --e{715}*/
752 assert( result != NULL );
753
755
756 return SCIP_OKAY;
757}
758
759/** creates the Gomory MIR cut separator and includes it in SCIP */
761 SCIP* scip /**< SCIP data structure */
762 )
763{
765 SCIP_SEPA* sepa;
766
767 /* create separator data */
769 sepadata->lastncutsfound = 0;
770
771 /* include separator */
774 sepaExeclpGomory, NULL,
775 sepadata) );
776 assert(sepa != NULL);
777
778 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepadata->strongcg, "strongcg", "separator for strong CG cuts", -100000, SEPA_FREQ, 0.0,
779 SEPA_USESSUBSCIP, FALSE, sepaExeclpDummy, sepaExecsolDummy, NULL) );
780 assert(sepadata->strongcg != NULL);
781
782 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepadata->gomory, "gomorymi", "separator for Gomory mixed-integer cuts", -100000, SEPA_FREQ, 0.0,
783 SEPA_USESSUBSCIP, FALSE, sepaExeclpDummy, sepaExecsolDummy, NULL) );
784 assert(sepadata->gomory != NULL);
785
786 /* set non-NULL pointers to callback methods */
787 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyGomory) );
788 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeGomory) );
789 SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitGomory) );
790 SCIP_CALL( SCIPsetSepaExit(scip, sepa, sepaExitGomory) );
791
792 /* mark main separator as a parent */
794
795 /* set pointer from child separators to main separator */
796 SCIPsetSepaParentsepa(scip, sepadata->strongcg, sepa);
797 SCIPsetSepaParentsepa(scip, sepadata->gomory, sepa);
798
799 /* add separator parameters */
801 "separating/gomory/maxrounds",
802 "maximal number of gomory separation rounds per node (-1: unlimited)",
803 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
805 "separating/gomory/maxroundsroot",
806 "maximal number of gomory separation rounds in the root node (-1: unlimited)",
807 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
809 "separating/gomory/maxsepacuts",
810 "maximal number of gomory cuts separated per separation round",
811 &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
813 "separating/gomory/maxsepacutsroot",
814 "maximal number of gomory cuts separated per separation round in the root node",
815 &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
817 "separating/gomory/maxrank",
818 "maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited)",
819 &sepadata->maxrank, FALSE, DEFAULT_MAXRANK, -1, INT_MAX, NULL, NULL) );
821 "separating/gomory/maxrankintegral",
822 "maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited)",
823 &sepadata->maxrankintegral, FALSE, DEFAULT_MAXRANKINTEGRAL, -1, INT_MAX, NULL, NULL) );
825 "separating/gomory/away",
826 "minimal integrality violation of a basis variable in order to try Gomory cut",
827 &sepadata->away, FALSE, DEFAULT_AWAY, 1e-4, 0.5, NULL, NULL) );
829 "separating/gomory/dynamiccuts",
830 "should generated cuts be removed from the LP if they are no longer tight?",
831 &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
833 "separating/gomory/makeintegral",
834 "try to scale cuts to integral coefficients",
835 &sepadata->makeintegral, TRUE, DEFAULT_MAKEINTEGRAL, NULL, NULL) );
837 "separating/gomory/forcecuts",
838 "if conversion to integral coefficients failed still consider the cut",
839 &sepadata->forcecuts, TRUE, DEFAULT_FORCECUTS, NULL, NULL) );
841 "separating/gomory/separaterows",
842 "separate rows with integral slack",
843 &sepadata->separaterows, TRUE, DEFAULT_SEPARATEROWS, NULL, NULL) );
845 "separating/gomory/delayedcuts",
846 "should cuts be added to the delayed cut pool?",
847 &sepadata->delayedcuts, TRUE, DEFAULT_DELAYEDCUTS, NULL, NULL) );
849 "separating/gomory/sidetypebasis",
850 "choose side types of row (lhs/rhs) based on basis information?",
851 &sepadata->sidetypebasis, TRUE, DEFAULT_SIDETYPEBASIS, NULL, NULL) );
853 "separating/gomory/trystrongcg",
854 "try to generate strengthened Chvatal-Gomory cuts?",
855 &sepadata->trystrongcg, TRUE, DEFAULT_TRYSTRONGCG, NULL, NULL) );
857 "separating/gomory/genbothgomscg",
858 "Should both Gomory and strong CG cuts be generated (otherwise take best)?",
859 &sepadata->genbothgomscg, TRUE, DEFAULT_GENBOTHGOMSCG, NULL, NULL) );
860
861 return SCIP_OKAY;
862}
#define BOUNDSWITCH
#define POSTPROCESS
#define USEVBDS
#define DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDS
#define DEFAULT_RANDSEED
methods for the aggregation rows
#define NULL
Definition def.h:266
#define SCIP_MAXSTRLEN
Definition def.h:287
#define SCIP_Longint
Definition def.h:157
#define SCIP_Bool
Definition def.h:91
#define MIN(x, y)
Definition def.h:242
#define SCIP_Real
Definition def.h:172
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_LONGINT_FORMAT
Definition def.h:164
#define SCIP_CALL(x)
Definition def.h:373
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
#define SCIPdebugMsg
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
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
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
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition lp.c:17070
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition lp.c:17024
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition scip_cut.c:361
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition scip_cut.c:94
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition cuts.c:1723
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:8966
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
Definition scip_cut.c:343
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition scip_cut.c:135
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition cuts.c:1755
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition scip_cut.c:250
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:2279
SCIP_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
Definition scip_cut.c:641
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:3873
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition scip_lp.c:686
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition scip_lp.c:471
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition scip_lp.c:570
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition scip_lp.c:667
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition scip_lp.c:714
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition lp.c:17419
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1922
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition lp.c:17320
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1904
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition lp.c:17439
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1635
int SCIProwGetNNonz(SCIP_ROW *row)
Definition lp.c:17241
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1993
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition lp.c:17330
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition lp.c:17296
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1658
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_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition scip_lp.c:1701
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:2104
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1562
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
int SCIProwGetRank(SCIP_ROW *row)
Definition lp.c:17409
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition lp.c:17562
int SCIPgetRowNumIntCols(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1886
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:115
int SCIPsepaGetFreq(SCIP_SEPA *sepa)
Definition sepa.c:787
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:173
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition sepa.c:743
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition sepa.c:880
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:205
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:189
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition sepa.c:633
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition sepa.c:643
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:157
void SCIPsetSepaIsParentsepa(SCIP *scip, SCIP_SEPA *sepa)
Definition scip_sepa.c:309
void SCIPsetSepaParentsepa(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPA *parentsepa)
Definition scip_sepa.c:324
int SCIPgetMaxDepth(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
int SCIPgetNCutsFound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPincVarGMISumScore(SCIP *scip, SCIP_VAR *var, SCIP_Real gmieff)
Definition scip_var.c:10015
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17611
SCIP_RETCODE SCIPsetVarLastGMIScore(SCIP *scip, SCIP_VAR *var, SCIP_Real gmieff)
Definition scip_var.c:10069
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition misc.c:10133
SCIP_RETCODE SCIPincludeSepaGomory(SCIP *scip)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10880
return SCIP_OKAY
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIP_Longint ncalls
int c
int maxdepth
int depth
SCIP_Bool cutoff
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
SCIP_Real frac
static SCIP_VAR ** vars
memory allocation routines
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for separator plugins
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
#define SEPA_PRIORITY
#define SEPA_DELAY
#define DEFAULT_DYNAMICCUTS
#define SEPA_DESC
#define MAKECONTINTEGRAL
#define SEPA_USESSUBSCIP
#define SEPA_MAXBOUNDDIST
#define SEPA_FREQ
#define SEPA_NAME
#define FIXINTEGRALRHS
Definition sepa_cgmip.c:172
#define MAXAGGRLEN(nvars)
Definition sepa_cgmip.c:178
#define DEFAULT_MAXRANKINTEGRAL
#define DEFAULT_MAXRANK
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)
#define DEFAULT_TRYSTRONGCG
#define DEFAULT_MAKEINTEGRAL
#define DEFAULT_DELAYEDCUTS
#define DEFAULT_SIDETYPEBASIS
static SCIP_RETCODE evaluateCutNumerics(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW *cut, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool *useful)
#define DEFAULT_AWAY
#define DEFAULT_FORCECUTS
#define DEFAULT_SEPARATEROWS
#define DEFAULT_GENBOTHGOMSCG
Gomory MIR Cuts.
struct SCIP_AggrRow SCIP_AGGRROW
Definition type_cuts.h:37
struct SCIP_Row SCIP_ROW
Definition type_lp.h:104
struct SCIP_Col SCIP_COL
Definition type_lp.h:98
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
struct SCIP_RandNumGen SCIP_RANDNUMGEN
Definition type_misc.h:126
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_SEPARATED
Definition type_result.h:49
enum SCIP_Retcode SCIP_RETCODE
struct Scip SCIP
Definition type_scip.h:39
struct SCIP_SepaData SCIP_SEPADATA
Definition type_sepa.h:52
#define SCIP_DECL_SEPAEXECSOL(x)
Definition type_sepa.h:166
#define SCIP_DECL_SEPAEXECLP(x)
Definition type_sepa.h:136
#define SCIP_DECL_SEPAFREE(x)
Definition type_sepa.h:69
#define SCIP_DECL_SEPAEXIT(x)
Definition type_sepa.h:85
struct SCIP_Sepa SCIP_SEPA
Definition type_sepa.h:51
#define SCIP_DECL_SEPACOPY(x)
Definition type_sepa.h:61
#define SCIP_DECL_SEPAINIT(x)
Definition type_sepa.h:77
struct SCIP_Var SCIP_VAR
Definition type_var.h:119
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71