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-2023 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/sepa_gomory.h"
82#include <string.h>
83
84#define SEPA_NAME "gomory"
85#define SEPA_DESC "separator for Gomory mixed-integer and strong CG cuts from LP tableau rows"
86#define SEPA_PRIORITY -1000
87#define SEPA_FREQ 10
88#define SEPA_MAXBOUNDDIST 1.0
89#define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
90#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
91
92#define DEFAULT_MAXROUNDS 5 /**< maximal number of gomory separation rounds per node (-1: unlimited) */
93#define DEFAULT_MAXROUNDSROOT 10 /**< maximal number of gomory separation rounds in the root node (-1: unlimited) */
94#define DEFAULT_MAXSEPACUTS 50 /**< maximal number of gomory cuts separated per separation round */
95#define DEFAULT_MAXSEPACUTSROOT 200 /**< maximal number of gomory cuts separated per separation round in root node */
96#define DEFAULT_MAXRANK -1 /**< maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited) */
97#define DEFAULT_MAXRANKINTEGRAL -1 /**< maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited) */
98#define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
99#define DEFAULT_AWAY 0.01 /**< minimal integrality violation of a basis variable in order to try Gomory cut */
100#define DEFAULT_MAKEINTEGRAL FALSE /**< try to scale all cuts to integral coefficients */
101#define DEFAULT_FORCECUTS TRUE /**< if conversion to integral coefficients failed still consider the cut */
102#define DEFAULT_SEPARATEROWS TRUE /**< separate rows with integral slack */
103#define DEFAULT_DELAYEDCUTS FALSE /**< should cuts be added to the delayed cut pool? */
104#define DEFAULT_SIDETYPEBASIS TRUE /**< choose side types of row (lhs/rhs) based on basis information? */
105#define DEFAULT_TRYSTRONGCG TRUE /**< try to generate strengthened Chvatal-Gomory cuts? */
106#define DEFAULT_GENBOTHGOMSCG TRUE /**< should both Gomory and strong CG cuts be generated (otherwise take best) */
107#define DEFAULT_RANDSEED 53 /**< initial random seed */
108
109#define BOUNDSWITCH 0.9999 /**< threshold for bound switching - see SCIPcalcMIR() */
110#define POSTPROCESS TRUE /**< apply postprocessing after MIR calculation - see SCIPcalcMIR() */
111#define USEVBDS TRUE /**< use variable bounds - see SCIPcalcMIR() */
112#define FIXINTEGRALRHS FALSE /**< try to generate an integral rhs - see SCIPcalcMIR() */
113#define MAKECONTINTEGRAL FALSE /**< convert continuous variable to integral variables in SCIPmakeRowIntegral() */
114
115#define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) /**< maximal length of base inequality */
116
117
118/** separator data */
119struct SCIP_SepaData
120{
121 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
122 SCIP_SEPA* strongcg; /**< strong CG cut separator */
123 SCIP_SEPA* gomory; /**< gomory cut separator */
124 SCIP_Real away; /**< minimal integrality violation of a basis variable in order to try Gomory cut */
125 int maxrounds; /**< maximal number of gomory separation rounds per node (-1: unlimited) */
126 int maxroundsroot; /**< maximal number of gomory separation rounds in the root node (-1: unlimited) */
127 int maxsepacuts; /**< maximal number of gomory cuts separated per separation round */
128 int maxsepacutsroot; /**< maximal number of gomory cuts separated per separation round in root node */
129 int maxrank; /**< maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited) */
130 int maxrankintegral; /**< maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited) */
131 int lastncutsfound; /**< total number of cuts found after last call of separator */
132 SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
133 SCIP_Bool makeintegral; /**< try to scale all cuts to integral coefficients */
134 SCIP_Bool forcecuts; /**< if conversion to integral coefficients failed still consider the cut */
135 SCIP_Bool separaterows; /**< separate rows with integral slack */
136 SCIP_Bool delayedcuts; /**< should cuts be added to the delayed cut pool? */
137 SCIP_Bool sidetypebasis; /**< choose side types of row (lhs/rhs) based on basis information? */
138 SCIP_Bool trystrongcg; /**< try to generate strengthened Chvatal-Gomory cuts? */
139 SCIP_Bool genbothgomscg; /**< should both Gomory and strong CG cuts be generated (otherwise take best) */
140};
141
142
143/** returns TRUE if the cut can be taken, otherwise FALSE if there some numerical evidences */
144static
146 SCIP* scip, /**< SCIP data structure */
147 SCIP_SEPADATA* sepadata, /**< data of the separator */
148 SCIP_ROW* cut, /**< cut to check */
149 SCIP_Longint maxdnom, /**< maximal denominator to use for scaling */
150 SCIP_Real maxscale, /**< maximal scaling factor */
151 SCIP_Bool* useful /**< pointer to store if the cut is useful */
152 )
153{
154 SCIP_Bool madeintegral = FALSE;
155
156 assert(useful != NULL);
157
158 *useful = FALSE;
159
160 if( sepadata->makeintegral && SCIPgetRowNumIntCols(scip, cut) == SCIProwGetNNonz(cut) )
161 {
162 /* try to scale the cut to integral values */
165
166 if( !madeintegral && !sepadata->forcecuts )
167 return SCIP_OKAY;
168
169 /* 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 return SCIP_OKAY;
172 }
173
174 /* discard integral cut if the rank is too high */
175 if( madeintegral && sepadata->maxrankintegral != -1 && (SCIProwGetRank(cut) > sepadata->maxrankintegral) )
176 return SCIP_OKAY;
177
178 /* discard cut if the rank is too high */
179 if( !madeintegral && (sepadata->maxrank != -1) && (SCIProwGetRank(cut) > sepadata->maxrank) )
180 return SCIP_OKAY;
181
182 *useful = TRUE;
183
184 return SCIP_OKAY;
185}
186
187
188/** add cut */
189static
191 SCIP* scip, /**< SCIP instance */
192 SCIP_SEPADATA* sepadata, /**< separator data */
193 SCIP_VAR** vars, /**< array of variables */
194 int c, /**< index of basic variable (< 0 for slack variables) */
195 SCIP_Longint maxdnom, /**< maximal denominator to use for scaling */
196 SCIP_Real maxscale, /**< maximal scaling factor */
197 int cutnnz, /**< number of nonzeros in cut */
198 int* cutinds, /**< variable indices in cut */
199 SCIP_Real* cutcoefs, /**< cut cofficients */
200 SCIP_Real cutefficacy, /**< cut efficacy */
201 SCIP_Real cutrhs, /**< rhs of cut */
202 SCIP_Bool cutislocal, /**< whether cut is local */
203 int cutrank, /**< rank of cut */
204 SCIP_Bool strongcg, /**< whether the cut arises from the strong-CG procedure */
205 SCIP_Bool* cutoff, /**< pointer to store whether a cutoff appeared */
206 int* naddedcuts /**< pointer to store number of added cuts */
207 )
208{
209 assert(scip != NULL);
210 assert(cutoff != NULL);
212
213 if( cutnnz == 0 && SCIPisFeasNegative(scip, cutrhs) ) /*lint !e644*/
214 {
215 SCIPdebugMsg(scip, " -> gomory cut detected infeasibility with cut 0 <= %g.\n", cutrhs);
216 *cutoff = TRUE;
217 return SCIP_OKAY;
218 }
219
220 /* Only take efficient cuts, except for cuts with one non-zero coefficient (= bound
221 * changes); the latter cuts will be handled internally in sepastore. */
223 {
224 SCIP_ROW* cut;
227 int v;
228
229 /* construct cut name */
230 if( strongcg )
231 {
232 cutsepa = sepadata->strongcg;
233
234 if( c >= 0 )
236 else
238 }
239 else
240 {
241 cutsepa = sepadata->gomory;
242
243 if( c >= 0 )
245 else
247 }
248
249 /* create empty cut */
251 cutislocal, FALSE, sepadata->dynamiccuts) );
252
253 /* set cut rank */
254 SCIProwChgRank(cut, cutrank); /*lint !e644*/
255
256 /* cache the row extension and only flush them if the cut gets added */
258
259 /* collect all non-zero coefficients */
260 for( v = 0; v < cutnnz; ++v )
261 {
263 }
264
265 /* flush all changes before adding the cut */
267
268 if( SCIProwGetNNonz(cut) == 0 )
269 {
271 SCIPdebugMsg(scip, " -> gomory cut detected infeasibility with cut 0 <= %g.\n", cutrhs);
272 *cutoff = TRUE;
273 return SCIP_OKAY;
274 }
275 else if( SCIProwGetNNonz(cut) == 1 )
276 {
277 /* Add the bound change as cut to avoid that the LP gets modified. This would mean that the LP is not flushed
278 * and the method SCIPgetLPBInvRow() fails; SCIP internally will apply this bound change automatically. */
280 ++(*naddedcuts);
281 }
282 else
283 {
284 SCIP_Bool useful;
285
288
289 SCIPdebugMsg(scip, " -> %s cut <%s>: rhs=%f, eff=%f\n", strongcg ? "strong-CG" : "gomory", cutname, cutrhs, cutefficacy);
290
292
293 if( useful )
294 {
295 SCIPdebugMsg(scip, " -> found %s cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
296 strongcg ? "strong-CG" : "gomory", cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut),
300
301 if( SCIPisCutNew(scip, cut) )
302 {
303 /* add global cuts which are not implicit bound changes to the cut pool */
304 if( !cutislocal )
305 {
306 if( sepadata->delayedcuts )
307 {
309 }
310 else
311 {
313 }
314 }
315 else
316 {
317 /* local cuts we add to the sepastore */
319 }
320
321 ++(*naddedcuts);
322 }
323 }
324 }
325 /* release the row */
327 }
328
329 return SCIP_OKAY;
330}
331
332/*
333 * Callback methods
334 */
335
336/** copy method for separator plugins (called when SCIP copies plugins) */
337static
339{ /*lint --e{715}*/
340 assert(scip != NULL);
341 assert(sepa != NULL);
343
344 /* call inclusion method of separator */
346
347 return SCIP_OKAY;
348}
349
350/** destructor of separator to free user data (called when SCIP is exiting) */
351/**! [SnippetSepaFreeGomory] */
352static
354{ /*lint --e{715}*/
356
358
359 /* free separator data */
361 assert(sepadata != NULL);
362
364
365 SCIPsepaSetData(sepa, NULL);
366
367 return SCIP_OKAY;
368}
369/**! [SnippetSepaFreeGomory] */
370
371/** initialization method of separator (called after problem was transformed) */
372static
374{
376
378 assert(sepadata != NULL);
379
380 /* create and initialize random number generator */
382
383 return SCIP_OKAY;
384}
385
386/** deinitialization method of separator (called before transformed problem is freed) */
387static
389{ /*lint --e{715}*/
391
393 assert(sepadata != NULL);
394
395 SCIPfreeRandom(scip, &sepadata->randnumgen);
396
397 return SCIP_OKAY;
398}
399
400
401/** LP solution separation method of separator */
402static
404{ /*lint --e{715}*/
406 SCIP_VAR** vars;
407 SCIP_COL** cols;
408 SCIP_ROW** rows;
409 SCIP_AGGRROW* aggrrow;
410 SCIP_Real* binvrow;
411 SCIP_Real* cutcoefs;
412 SCIP_Real* basisfrac;
413 int* basisind;
414 int* basisperm;
415 int* inds;
416 int* cutinds;
417 SCIP_Real maxscale;
418 SCIP_Real minfrac;
419 SCIP_Real maxfrac;
420 SCIP_Longint maxdnom;
421 SCIP_Bool cutoff;
422 SCIP_Bool separatescg;
423 SCIP_Bool separategmi;
424 int naddedcuts;
425 int nvars;
426 int ncols;
427 int nrows;
428 int ncalls;
429 int maxdepth;
430 int maxsepacuts;
431 int freq;
432 int c;
433 int i;
434
435 assert(sepa != NULL);
437 assert(scip != NULL);
438 assert(result != NULL);
439
441
443 assert(sepadata != NULL);
444
446
447 minfrac = sepadata->away;
448 maxfrac = 1.0 - sepadata->away;
449
450 /* only call separator, if we are not close to terminating */
451 if( SCIPisStopped(scip) )
452 return SCIP_OKAY;
453
454 /* only call the gomory cut separator a given number of times at each node */
455 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
456 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
457 return SCIP_OKAY;
458
459 /* only call separator, if an optimal LP solution is at hand */
461 return SCIP_OKAY;
462
463 /* only call separator, if the LP solution is basic */
464 if( !SCIPisLPSolBasic(scip) )
465 return SCIP_OKAY;
466
467 /* only call separator, if there are fractional variables */
468 if( SCIPgetNLPBranchCands(scip) == 0 )
469 return SCIP_OKAY;
470
471 /* check whether strong CG cuts should be separated */
472 freq = SCIPsepaGetFreq(sepadata->strongcg);
473 if( freq > 0 )
474 separatescg = (depth % freq == 0);
475 else
476 separatescg = (freq == depth);
477
478 /* check whether Gomory MI cuts should be separated */
479 freq = SCIPsepaGetFreq(sepadata->gomory);
480 if( freq > 0 )
481 separategmi = (depth % freq == 0);
482 else
483 separategmi = (freq == depth);
484
485 if( !separatescg && !separategmi )
486 return SCIP_OKAY;
487
488 /* get variables data */
490
491 /* get LP data */
492 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
493 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
494 if( ncols == 0 || nrows == 0 )
495 return SCIP_OKAY;
496
497 /* set the maximal denominator in rational representation of gomory cut and the maximal scale factor to
498 * scale resulting cut to integral values to avoid numerical instabilities
499 */
500 /**@todo find better but still stable gomory cut settings: look at dcmulti, gesa3, khb0525, misc06, p2756 */
502 if( depth == 0 )
503 {
504 maxdnom = 1000;
505 maxscale = 1000.0;
506 }
507 else if( depth <= maxdepth/4 )
508 {
509 maxdnom = 1000;
510 maxscale = 1000.0;
511 }
512 else if( depth <= maxdepth/2 )
513 {
514 maxdnom = 100;
515 maxscale = 100.0;
516 }
517 else
518 {
519 maxdnom = 10;
520 maxscale = 10.0;
521 }
522
523 /* allocate temporary memory */
530 SCIP_CALL( SCIPallocBufferArray(scip, &inds, nrows) );
531 SCIP_CALL( SCIPaggrRowCreate(scip, &aggrrow) );
532
533 /* get basis indices */
535
536 for( i = 0; i < nrows; ++i )
537 {
538 SCIP_Real frac = 0.0;
539
540 c = basisind[i];
541
542 basisperm[i] = i;
543
544 if( c >= 0 )
545 {
546 SCIP_VAR* var;
547
548 assert(c < ncols);
549 var = SCIPcolGetVar(cols[c]);
551 {
553 frac = MIN(frac, 1.0 - frac);
554 }
555 }
556 else if( sepadata->separaterows )
557 {
558 SCIP_ROW* row;
559
560 assert(0 <= -c-1 && -c-1 < nrows);
561 row = rows[-c-1];
562 if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
563 {
565 frac = MIN(frac, 1.0 - frac);
566 }
567 }
568
569 if( frac >= minfrac )
570 {
571 /* slightly change fractionality to have random order for equal fractions */
572 basisfrac[i] = frac + SCIPrandomGetReal(sepadata->randnumgen, -1e-6, 1e-6);
573 }
574 else
575 {
576 basisfrac[i] = 0.0;
577 }
578 }
579
580 /* sort basis indices by fractionality */
582
583 /* get the maximal number of cuts allowed in a separation round */
584 if( depth == 0 )
585 maxsepacuts = sepadata->maxsepacutsroot;
586 else
587 maxsepacuts = sepadata->maxsepacuts;
588
589 SCIPdebugMsg(scip, "searching gomory cuts: %d cols, %d rows, maxdnom=%" SCIP_LONGINT_FORMAT ", maxscale=%g, maxcuts=%d\n",
590 ncols, nrows, maxdnom, maxscale, maxsepacuts);
591
592 cutoff = FALSE;
593 naddedcuts = 0;
594
595 /* for all basic columns belonging to integer variables, try to generate a gomory cut */
596 for( i = 0; i < nrows && naddedcuts < maxsepacuts && !SCIPisStopped(scip) && !cutoff; ++i )
597 {
598 SCIP_Real cutrhs;
599 SCIP_Real cutefficacy = 0.0;
600 SCIP_Bool success;
601 SCIP_Bool cutislocal;
602 SCIP_Bool strongcgsuccess = FALSE;
603 int ninds = -1;
604 int cutnnz;
605 int cutrank;
606 int j;
607
608 if( basisfrac[i] == 0.0 )
609 break;
610
611 j = basisperm[i];
612 c = basisind[j];
613
614 /* get the row of B^-1 for this basic integer variable with fractional solution value */
616
618 sepadata->sidetypebasis, allowlocal, 2, (int) MAXAGGRLEN(nvars), &success) );
619
620 if( !success )
621 continue;
622
623 /* try to create a strong CG cut out of the aggregation row */
624 if( separatescg )
625 {
628
629 /* if we want to generate both cuts, add cut and reset cutefficacy and strongcgsuccess */
630 if( strongcgsuccess && sepadata->genbothgomscg )
631 {
632 assert(allowlocal || !cutislocal); /*lint !e644*/
635 cutefficacy = 0.0;
637 if( cutoff )
638 break;
639 }
640 }
641
642 /* @todo Currently we are using the SCIPcalcMIR() function to compute the coefficients of the Gomory
643 * cut. Alternatively, we could use the direct version (see thesis of Achterberg formula (8.4)) which
644 * leads to cut a of the form \sum a_i x_i \geq 1. Rumor has it that these cuts are better.
645 */
646
647 /* try to create Gomory cut out of the aggregation row */
648 if( separategmi )
649 {
650 /* SCIPcalcMIR will only override the cut if its efficacy is larger than the one of the strongcg cut */
653
654 if( success || strongcgsuccess )
655 {
656 assert(allowlocal || !cutislocal); /*lint !e644*/
657 if( success )
658 strongcgsuccess = FALSE; /* Set strongcgsuccess to FALSE, since the MIR cut has overriden the strongcg cut. */
659
662 }
663 }
664 }
665
666 /* free temporary memory */
674 SCIPaggrRowFree(scip, &aggrrow);
675
676 SCIPdebugMsg(scip, "end searching gomory cuts: found %d cuts\n", naddedcuts);
677
678 sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
679
680 /* evaluate the result of the separation */
681 if( cutoff )
683 else if ( naddedcuts > 0 )
685 else
687
688 return SCIP_OKAY;
689}
690
691
692/*
693 * separator specific interface methods
694 */
695
696/** LP solution separation method of dummy separator */
697static
699{ /*lint --e{715}*/
700 assert( result != NULL );
701
703
704 return SCIP_OKAY;
705}
706
707/** arbitrary primal solution separation method of dummy separator */
708static
710{ /*lint --e{715}*/
711 assert( result != NULL );
712
714
715 return SCIP_OKAY;
716}
717
718/** creates the Gomory MIR cut separator and includes it in SCIP */
720 SCIP* scip /**< SCIP data structure */
721 )
722{
724 SCIP_SEPA* sepa;
725
726 /* create separator data */
728 sepadata->lastncutsfound = 0;
729
730 /* include separator */
734 sepadata) );
735 assert(sepa != NULL);
736
737 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepadata->strongcg, "strongcg", "separator for strong CG cuts", -100000, SEPA_FREQ, 0.0,
739 assert(sepadata->strongcg != NULL);
740
741 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepadata->gomory, "gomorymi", "separator for Gomory mixed-integer cuts", -100000, SEPA_FREQ, 0.0,
743 assert(sepadata->gomory != NULL);
744
745 /* set non-NULL pointers to callback methods */
750
751 /* mark main separator as a parent */
753
754 /* set pointer from child separators to main separator */
755 SCIPsetSepaParentsepa(scip, sepadata->strongcg, sepa);
756 SCIPsetSepaParentsepa(scip, sepadata->gomory, sepa);
757
758 /* add separator parameters */
760 "separating/gomory/maxrounds",
761 "maximal number of gomory separation rounds per node (-1: unlimited)",
762 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
764 "separating/gomory/maxroundsroot",
765 "maximal number of gomory separation rounds in the root node (-1: unlimited)",
766 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
768 "separating/gomory/maxsepacuts",
769 "maximal number of gomory cuts separated per separation round",
770 &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
772 "separating/gomory/maxsepacutsroot",
773 "maximal number of gomory cuts separated per separation round in the root node",
774 &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
776 "separating/gomory/maxrank",
777 "maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited)",
778 &sepadata->maxrank, FALSE, DEFAULT_MAXRANK, -1, INT_MAX, NULL, NULL) );
780 "separating/gomory/maxrankintegral",
781 "maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited)",
782 &sepadata->maxrankintegral, FALSE, DEFAULT_MAXRANKINTEGRAL, -1, INT_MAX, NULL, NULL) );
784 "separating/gomory/away",
785 "minimal integrality violation of a basis variable in order to try Gomory cut",
786 &sepadata->away, FALSE, DEFAULT_AWAY, 1e-4, 0.5, NULL, NULL) );
788 "separating/gomory/dynamiccuts",
789 "should generated cuts be removed from the LP if they are no longer tight?",
790 &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
792 "separating/gomory/makeintegral",
793 "try to scale cuts to integral coefficients",
794 &sepadata->makeintegral, TRUE, DEFAULT_MAKEINTEGRAL, NULL, NULL) );
796 "separating/gomory/forcecuts",
797 "if conversion to integral coefficients failed still consider the cut",
798 &sepadata->forcecuts, TRUE, DEFAULT_FORCECUTS, NULL, NULL) );
800 "separating/gomory/separaterows",
801 "separate rows with integral slack",
802 &sepadata->separaterows, TRUE, DEFAULT_SEPARATEROWS, NULL, NULL) );
804 "separating/gomory/delayedcuts",
805 "should cuts be added to the delayed cut pool?",
806 &sepadata->delayedcuts, TRUE, DEFAULT_DELAYEDCUTS, NULL, NULL) );
808 "separating/gomory/sidetypebasis",
809 "choose side types of row (lhs/rhs) based on basis information?",
810 &sepadata->sidetypebasis, TRUE, DEFAULT_SIDETYPEBASIS, NULL, NULL) );
812 "separating/gomory/trystrongcg",
813 "try to generate strengthened Chvatal-Gomory cuts?",
814 &sepadata->trystrongcg, TRUE, DEFAULT_TRYSTRONGCG, NULL, NULL) );
816 "separating/gomory/genbothgomscg",
817 "Should both Gomory and strong CG cuts be generated (otherwise take best)?",
818 &sepadata->genbothgomscg, TRUE, DEFAULT_GENBOTHGOMSCG, NULL, NULL) );
819
820 return SCIP_OKAY;
821}
methods for the aggregation rows
#define SCIP_MAXSTRLEN
Definition def.h:302
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_CALL(x)
Definition def.h:388
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:17042
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition lp.c:16996
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:1731
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
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:1763
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:2287
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:3879
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:17391
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1922
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition lp.c:17292
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1904
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition lp.c:17411
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1635
int SCIProwGetNNonz(SCIP_ROW *row)
Definition lp.c:17213
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1993
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition lp.c:17302
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition lp.c:17268
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:17381
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition lp.c:17534
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:109
int SCIPsepaGetFreq(SCIP_SEPA *sepa)
Definition sepa.c:787
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:167
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:199
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:183
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:151
void SCIPsetSepaIsParentsepa(SCIP *scip, SCIP_SEPA *sepa)
Definition scip_sepa.c:303
void SCIPsetSepaParentsepa(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPA *parentsepa)
Definition scip_sepa.c:318
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_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition misc.c:10041
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:10788
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
#define NULL
Definition lpi_spx1.cpp:161
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
#define SEPA_PRIORITY
Definition sepa_gomory.c:86
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 BOUNDSWITCH
#define SEPA_DELAY
Definition sepa_gomory.c:90
#define DEFAULT_DYNAMICCUTS
Definition sepa_gomory.c:98
#define DEFAULT_MAKEINTEGRAL
#define POSTPROCESS
#define SEPA_DESC
Definition sepa_gomory.c:85
#define DEFAULT_MAXRANKINTEGRAL
Definition sepa_gomory.c:97
#define MAKECONTINTEGRAL
#define DEFAULT_MAXROUNDSROOT
Definition sepa_gomory.c:93
#define SEPA_USESSUBSCIP
Definition sepa_gomory.c:89
#define DEFAULT_DELAYEDCUTS
#define DEFAULT_SIDETYPEBASIS
#define FIXINTEGRALRHS
#define DEFAULT_MAXSEPACUTSROOT
Definition sepa_gomory.c:95
#define USEVBDS
#define DEFAULT_MAXRANK
Definition sepa_gomory.c:96
#define SEPA_MAXBOUNDDIST
Definition sepa_gomory.c:88
static SCIP_RETCODE evaluateCutNumerics(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW *cut, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool *useful)
#define DEFAULT_AWAY
Definition sepa_gomory.c:99
#define DEFAULT_FORCECUTS
#define SEPA_FREQ
Definition sepa_gomory.c:87
#define DEFAULT_RANDSEED
#define MAXAGGRLEN(nvars)
#define DEFAULT_MAXSEPACUTS
Definition sepa_gomory.c:94
#define SEPA_NAME
Definition sepa_gomory.c:84
#define DEFAULT_MAXROUNDS
Definition sepa_gomory.c:92
#define DEFAULT_SEPARATEROWS
#define DEFAULT_GENBOTHGOMSCG
Gomory MIR Cuts.
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ 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_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
#define SCIP_DECL_SEPACOPY(x)
Definition type_sepa.h:61
#define SCIP_DECL_SEPAINIT(x)
Definition type_sepa.h:77
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71