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
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. */
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),
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 */
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) */
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}*/
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) */
373static
374SCIP_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) */
388static
389SCIP_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 */
403static
404SCIP_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 assert(c < ncols);
558 var = SCIPcolGetVar(cols[c]);
560 {
561 frac = SCIPfeasFrac(scip, SCIPcolGetPrimsol(cols[c]));
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 )
723 *result = SCIP_CUTOFF;
724 else if ( naddedcuts > 0 )
725 *result = SCIP_SEPARATED;
726 else
727 *result = SCIP_DIDNOTFIND;
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
743 *result = SCIP_DIDNOTRUN;
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
754 *result = SCIP_DIDNOTRUN;
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{
764 SCIP_SEPADATA* sepadata;
765 SCIP_SEPA* sepa;
766
767 /* create separator data */
768 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
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}
methods for the aggregation rows
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
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
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
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)
Definition: scip_branch.c:428
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: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: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 SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
Definition: scip_sepa.c:199
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
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:880
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:633
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:643
void SCIPsetSepaIsParentsepa(SCIP *scip, SCIP_SEPA *sepa)
Definition: scip_sepa.c:303
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
void SCIPsetSepaParentsepa(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPA *parentsepa)
Definition: scip_sepa.c:318
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: scip_sepa.c:183
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:9904
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_RETCODE SCIPsetVarLastGMIScore(SCIP *scip, SCIP_VAR *var, SCIP_Real gmieff)
Definition: scip_var.c:9958
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
SCIP_RETCODE SCIPincludeSepaGomory(SCIP *scip)
Definition: sepa_gomory.c:760
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
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
Definition: sepa_gomory.c:87
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
static SCIP_DECL_SEPAEXECLP(sepaExeclpGomory)
Definition: sepa_gomory.c:404
static SCIP_DECL_SEPAEXIT(sepaExitGomory)
Definition: sepa_gomory.c:389
#define DEFAULT_TRYSTRONGCG
Definition: sepa_gomory.c:106
#define BOUNDSWITCH
Definition: sepa_gomory.c:110
#define SEPA_DELAY
Definition: sepa_gomory.c:91
#define DEFAULT_DYNAMICCUTS
Definition: sepa_gomory.c:99
#define DEFAULT_MAKEINTEGRAL
Definition: sepa_gomory.c:101
#define POSTPROCESS
Definition: sepa_gomory.c:111
#define SEPA_DESC
Definition: sepa_gomory.c:86
#define DEFAULT_MAXRANKINTEGRAL
Definition: sepa_gomory.c:98
static SCIP_DECL_SEPAFREE(sepaFreeGomory)
Definition: sepa_gomory.c:354
#define MAKECONTINTEGRAL
Definition: sepa_gomory.c:114
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_gomory.c:94
#define SEPA_USESSUBSCIP
Definition: sepa_gomory.c:90
#define DEFAULT_DELAYEDCUTS
Definition: sepa_gomory.c:104
#define DEFAULT_SIDETYPEBASIS
Definition: sepa_gomory.c:105
#define FIXINTEGRALRHS
Definition: sepa_gomory.c:113
static SCIP_DECL_SEPACOPY(sepaCopyGomory)
Definition: sepa_gomory.c:339
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_gomory.c:96
#define USEVBDS
Definition: sepa_gomory.c:112
#define DEFAULT_MAXRANK
Definition: sepa_gomory.c:97
#define SEPA_MAXBOUNDDIST
Definition: sepa_gomory.c:89
static SCIP_DECL_SEPAINIT(sepaInitGomory)
Definition: sepa_gomory.c:374
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 DEFAULT_AWAY
Definition: sepa_gomory.c:100
#define DEFAULT_FORCECUTS
Definition: sepa_gomory.c:102
#define SEPA_FREQ
Definition: sepa_gomory.c:88
#define DEFAULT_RANDSEED
Definition: sepa_gomory.c:108
#define MAXAGGRLEN(nvars)
Definition: sepa_gomory.c:116
static SCIP_DECL_SEPAEXECSOL(sepaExecsolDummy)
Definition: sepa_gomory.c:750
#define DEFAULT_MAXSEPACUTS
Definition: sepa_gomory.c:95
#define SEPA_NAME
Definition: sepa_gomory.c:85
#define DEFAULT_MAXROUNDS
Definition: sepa_gomory.c:93
#define DEFAULT_SEPARATEROWS
Definition: sepa_gomory.c:103
#define DEFAULT_GENBOTHGOMSCG
Definition: sepa_gomory.c:107
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
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71