Scippy

SCIP

Solving Constraint Integer Programs

branch_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 branch_gomory.c
26 * @ingroup DEFPLUGINS_BRANCH
27 * @brief Gomory cut branching rule
28 * @author Mark Turner
29 *
30 * The approach is based on the following papers.
31 *
32 * M. Turner, T. Berthold, M. Besancon, T. Koch@n
33 * Branching via Cutting Plane Selection: Improving Hybrid Branching,@n
34 * arXiv preprint arXiv:2306.06050
35 *
36 * The Gomory cut branching rule selects a candidate integer variable $j$ with a fractional solution value.
37 * Each candidate variable must be a basic variable in the LP Tableau (if not then it would have to be at its bound
38 * that is integer-valued)
39 * This branching rule calculates the GMI cut for the aggregated row of the LP tableau associated with the
40 * candidate variable.
41 * The generated cut is then scored using a weighted sum rule.
42 * The branching candidate whose cut is highest scoring is then selected.
43 * For more details on the method, see:
44 *
45 * @par
46 * Mark Turner, Timo Berthold, Mathieu Besançon, Thorsten Koch@n
47 * Branching via Cutting Plane Selection: Improving Hybrid Branching@n
48 * 2023@n
49 */
50
51/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
52
53#include "scip/branch_gomory.h"
54#include "scip/pub_branch.h"
55#include "scip/pub_var.h"
56#include "scip/pub_lp.h"
57#include "scip/pub_tree.h"
58#include "scip/pub_message.h"
59#include "scip/scip_branch.h"
60#include "scip/scip_cut.h"
61#include "scip/scip_mem.h"
62#include "scip/scip_message.h"
63#include "scip/scip_numerics.h"
64#include "scip/scip_lp.h"
65#include "scip/scip_tree.h"
66#include "scip/scip_param.h"
68#include <string.h>
69#include <assert.h>
70
71
72
73#define BRANCHRULE_NAME "gomory"
74#define BRANCHRULE_DESC "Gomory cut score branching"
75#define BRANCHRULE_PRIORITY -1000
76#define BRANCHRULE_MAXDEPTH -1
77#define BRANCHRULE_MAXBOUNDDIST 1.0
78
79#define DEFAULT_MAXNCANDS -1 /**< maximum number of branching candidates to produce a cut for */
80#define DEFAULT_EFFICACYWEIGHT 1.0 /**< the weight of efficacy in weighted sum cut scoring rule */
81#define DEFAULT_OBJPARALLELWEIGHT 0.0 /**< the weight of objective parallelism in weighted sum scoring rule */
82#define DEFAULT_INTSUPPORTWEIGHT 0.0 /**< the weight of integer support in weighted sum cut scoring rule */
83#define DEFAULT_PERFORMRELPSCOST FALSE /**< if relpscost branching should be called without actual branching */
84#define DEFAULT_USEWEAKERCUTS TRUE /**< use weaker cuts derived from the exact branching split */
85
86
87/*
88 * Data structures
89 */
90
91/** branching rule data */
92struct SCIP_BranchruleData
93{
94 int maxncands; /**< maximum number of variable candidates to produce cut for */
95 SCIP_Real efficacyweight; /**< the weight of efficacy in weighted sum cut scoring rule */
96 SCIP_Real objparallelweight; /**< the weight of objective parallelism in weighted sum scoring rule */
97 SCIP_Real intsupportweight; /**< the weight of integer support in weighted sum cut scoring rule */
98 SCIP_Bool performrelpscost; /**< if relpscost branching should be called without actual branching */
99 SCIP_Bool useweakercuts; /**< use weaker cuts derived from the exact branching split */
100};
101
102
103/*
104 * Local methods
105 */
106
107/** Generate GMI cut: The GMI is given by
108 * sum(f_j x_j , j in J_I s.t. f_j <= f_0) +
109 * sum((1-f_j)*f_0/(1 - f_0) x_j, j in J_I s.t. f_j > f_0) +
110 * sum(a_j x_j, , j in J_C s.t. a_j >= 0) -
111 * sum(a_j*f_0/(1-f_0) x_j , j in J_C s.t. a_j < 0) >= f_0.
112 * where J_I are the integer non-basic variables and J_C are the continuous.
113 * f_0 is the fractional part of lpval
114 * a_j is the j-th coefficient of the tableau row and f_j its fractional part
115 * Note: we create -% <= -f_0 !!
116 * Note: this formula is valid for a problem of the form Ax = b, x>= 0. Since we do not have
117 * such problem structure in general, we have to (implicitly) transform whatever we are given
118 * to that form. Specifically, non-basic variables at their lower bound are shifted so that the lower
119 * bound is 0 and non-basic at their upper bound are complemented. */
120static
122 SCIP* scip, /**< SCIP data structure */
123 int ncols, /**< Number of columns (original variables) in the LP */
124 int nrows, /**< Number of rows (slack variables) in the LP */
125 SCIP_COL** cols, /**< Column data of the LP */
126 SCIP_ROW** rows, /**< Row data of the LP */
127 const SCIP_Real* binvrow, /**< row of B^-1 for current basic variable */
128 const SCIP_Real* binvarow, /**< row of B^-1A for current basic variable */
129 const SCIP_Real* lpval, /**< value of variable at current LP solution */
130 SCIP_Real* cutcoefs, /**< array to store cut coefficients */
131 SCIP_Real* cutrhs, /**< pointer to store rhs of cut */
132 SCIP_Bool useweakerscuts /**< use weakener cuts derived from the exact branching split */
133 )
134{
135 SCIP_COL** rowcols;
136 SCIP_COL* col;
137 SCIP_ROW* row;
138 SCIP_Real* rowvals;
139 SCIP_BASESTAT basestat;
140 SCIP_Real rowelem;
141 SCIP_Real cutelem;
142 SCIP_Real f0;
143 SCIP_Real f0complementratio;
144 SCIP_Real rowrhs;
145 SCIP_Real rowlhs;
146 SCIP_Real rowact;
147 SCIP_Real rowrhsslack;
148 int i;
149 int c;
150
151 /* Clear the memory array of cut coefficients. It may store that of the last computed cut */
152 BMSclearMemoryArray(cutcoefs, ncols);
153
154 /* compute fractionality f0 and f0/(1-f0) */
155 f0 = SCIPfeasFrac(scip, *lpval);
156 f0complementratio = f0 / (1.0 - f0);
157
158 /* The rhs of the cut is the fractional part of the LP solution of the basic variable */
159 *cutrhs = -f0;
160
161 /* Generate cut coefficient for the original variables */
162 for ( c = 0; c < ncols; c++ )
163 {
164 col = cols[c];
165 assert( col != NULL );
166
167 basestat = SCIPcolGetBasisStatus(col);
168 /* Get simplex tableau coefficient */
169 if ( basestat == SCIP_BASESTAT_LOWER )
170 {
171 /* Take coefficient if nonbasic at lower bound */
172 rowelem = binvarow[c];
173 }
174 else if ( basestat == SCIP_BASESTAT_UPPER )
175 {
176 /* Flip coefficient if nonbasic at upper bound: x --> u - x */
177 rowelem = -binvarow[c];
178 }
179 else
180 {
181 /* Nonbasic free variable at zero or basic variable. Just skip it. */
182 continue;
183 }
184
185 /* Integer variables */
186 if ( SCIPcolIsIntegral(col) && !useweakerscuts )
187 {
188 /* Warning: Because of numerics we can have cutelem < 0
189 * In such a case it is very close to 0, so isZero will catch and we can ignore the coefficient */
190 cutelem = SCIPfrac(scip, rowelem);
191 if ( cutelem > f0 )
192 {
193 /* sum((1 - f_j) * f_0/(1 - f_0) x_j, j in J_I s.t. f_j > f_0 */
194 cutelem = -((1.0 - cutelem) * f0complementratio);
195 }
196 else
197 {
198 /* sum(f_j * x_j, j in J_I s.t. f_j <= 0 */
199 cutelem = -cutelem;
200 }
201 }
202 /* Then continuous variables */
203 else
204 {
205 if ( rowelem < 0 )
206 {
207 /* sum(a_j* f_0/(1 - f_0) x_j, j in J_C s.t. a_j < 0 */
208 cutelem = rowelem * f0complementratio;
209 }
210 else
211 {
212 /* sum(a_j * x_j, j in J_C s.t. a_j >= 0 */
213 cutelem = -rowelem;
214 }
215 }
216
217 /* Cut is defined when variables are in [0, infinity). Translate to general bounds. */
218 if ( !SCIPisZero(scip, cutelem) )
219 {
220 if ( basestat == SCIP_BASESTAT_UPPER )
221 {
222 cutelem = -cutelem;
223 *cutrhs += cutelem * SCIPcolGetUb(col);
224 }
225 else
226 {
227 *cutrhs += cutelem * SCIPcolGetLb(col);
228 }
229 /* Add coefficient to cut */
230 cutcoefs[SCIPcolGetLPPos(col)] = cutelem;
231 }
232 }
233
234 /* generate cut coefficient for the slack variables. Skip the basic ones */
235 for ( c = 0; c < nrows; c++ )
236 {
237 row = rows[c];
238 assert( row != NULL );
239 basestat = SCIProwGetBasisStatus(row);
240
241 /* Get the simplex tableau coefficient */
242 if ( basestat == SCIP_BASESTAT_LOWER )
243 {
244 /* Take coefficient if nonbasic at lower bound */
245 rowelem = binvrow[SCIProwGetLPPos(row)];
246 /* If there is a >= constraint or ranged constraint at the lower bound, we have to flip the row element */
247 if ( !SCIPisInfinity(scip, -SCIProwGetLhs(row)) )
248 rowelem = -rowelem;
249 }
250 else if ( basestat == SCIP_BASESTAT_UPPER )
251 {
252 /* Take element if nonbasic at upper bound. Only non-positive slack variables can be nonbasic at upper,
253 * therefore they should be flipped twice, meaning we can take the element directly */
254 rowelem = binvrow[SCIProwGetLPPos(row)];
255 }
256 else
257 {
258 /* Nonbasic free variable at zero or basic variable. Free variable should not happen here. Just skip if free */
259 assert( basestat == SCIP_BASESTAT_BASIC );
260 continue;
261 }
262
263 /* Integer rows */
264 if ( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) && !useweakerscuts )
265 {
266 /* Warning: Because of numerics we can have cutelem < 0
267 * In such a case it is very close to 0, so isZero will catch and we can ignore the coefficient */
268 cutelem = SCIPfrac(scip, rowelem);
269 if ( cutelem > f0 )
270 {
271 /* sum((1 - f_j) * f_0/(1 - f_0) x_j, j in J_I s.t. f_j > f_0 */
272 cutelem = -((1.0 - cutelem) * f0complementratio);
273 }
274 else
275 {
276 /* sum(f_j * x_j, j in J_I s.t. f_j <= 0 */
277 cutelem = -cutelem;
278 }
279 }
280 /* Then continuous variables */
281 else
282 {
283 if ( rowelem < 0 )
284 {
285 /* sum(a_j* f_0/(1 - f_0) x_j, j in J_C s.t. a_j < 0 */
286 cutelem = rowelem * f0complementratio;
287 }
288 else
289 {
290 /* sum(a_j * x_j, j in J_C s.t. a_j >= 0 */
291 cutelem = -rowelem;
292 }
293 }
294
295 /* Cut is defined in original variables, so we replace slack variables by their original definition */
296 if ( !SCIPisZero(scip, cutelem) )
297 {
298 /* Coefficient is large enough so we keep it */
299 rowlhs = SCIProwGetLhs(row);
300 rowrhs = SCIProwGetRhs(row);
301 assert( SCIPisLE(scip, rowlhs, rowrhs) );
302 assert( !SCIPisInfinity(scip, rowlhs) || !SCIPisInfinity(scip, rowrhs) );
303
304 /* If the slack variable is fixed we can ignore this cut coefficient */
305 if ( SCIPisFeasZero(scip, rowrhs - rowlhs) )
306 continue;
307
308 /* Un-flip sack variable and adjust rhs if necessary.
309 * Row at lower basis means the slack variable is at its upper bound.
310 * Since SCIP adds +1 slacks, this can only happen when constraints have finite lhs */
312 {
313 assert( !SCIPisInfinity(scip, -rowlhs) );
314 cutelem = -cutelem;
315 }
316
317 rowcols = SCIProwGetCols(row);
318 rowvals = SCIProwGetVals(row);
319
320 /* Eliminate slack variables. rowcols is sorted [columns in LP, columns not in LP] */
321 for ( i = 0; i < SCIProwGetNLPNonz(row); i++ )
322 cutcoefs[SCIPcolGetLPPos(rowcols[i])] -= cutelem * rowvals[i];
323
324 /* Modify the rhs */
325 rowact = SCIPgetRowActivity(scip, row);
326 rowrhsslack = rowrhs - rowact;
327
328 if ( SCIPisFeasZero(scip, rowrhsslack) )
329 *cutrhs -= cutelem * (rowrhs - SCIProwGetConstant(row));
330 else
331 {
332 assert( SCIPisFeasZero(scip, rowact - rowlhs) );
333 *cutrhs -= cutelem * (rowlhs - SCIProwGetConstant(row));
334 }
335 }
336 }
337
338 return TRUE;
339}
340
341
342/*
343 * Callback methods of branching rule
344 */
345
346
347/** copy method for branchrule plugins (called when SCIP copies plugins) */
348static
349SCIP_DECL_BRANCHCOPY(branchCopyGomory)
350{ /*lint --e{715}*/
351 assert(scip != NULL);
352 assert(branchrule != NULL);
353 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
354
355 /* call inclusion method of branchrule */
357
358 return SCIP_OKAY;
359}
360
361
362/** destructor of branching rule to free user data (called when SCIP is exiting) */
363static
364SCIP_DECL_BRANCHFREE(branchFreeGomory)
365{ /*lint --e{715}*/
366 SCIP_BRANCHRULEDATA* branchruledata;
367
368 /* free branching rule data */
369 branchruledata = SCIPbranchruleGetData(branchrule);
370 assert(branchruledata != NULL);
371
372 SCIPfreeBlockMemoryNull(scip, &branchruledata);
373
374 return SCIP_OKAY;
375}
376
377
378/** branching execution method for fractional LP solutions */
379static
380SCIP_DECL_BRANCHEXECLP(branchExeclpGomory)
381{ /*lint --e{715}*/
382 SCIP_BRANCHRULEDATA* branchruledata;
383 SCIP_VAR** lpcands;
384 SCIP_COL** cols;
385 SCIP_ROW** rows;
386 SCIP_Real* lpcandssol;
387 SCIP_Real* lpcandsfrac;
388 SCIP_Real* binvrow;
389 SCIP_Real* binvarow;
390 SCIP_Real* cutcoefs;
391 SCIP_ROW* cut;
392 SCIP_COL* col;
393 int* basisind;
394 int* basicvarpos2tableaurow;
395 int* inds;
396 const char* name;
397 SCIP_Real cutrhs;
398 SCIP_Real score;
399 SCIP_Real bestscore;
400 SCIP_Bool success;
401 int nlpcands;
402 int maxncands;
403 int ncols;
404 int nrows;
405 int lppos;
406 int ninds;
407 int bestcand;
408 int i;
409 int j;
410
411 name = (char *) "test";
412
413 assert(branchrule != NULL);
414 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
415 assert(scip != NULL);
416 assert(result != NULL);
417
418 SCIPdebugMsg(scip, "Execlp method of Gomory branching in node %" SCIP_LONGINT_FORMAT "\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
419
421 {
422 *result = SCIP_DIDNOTRUN;
423 SCIPdebugMsg(scip, "Could not apply Gomory branching, as the current LP was not solved to optimality.\n");
424
425 return SCIP_OKAY;
426 }
427
428 /* Get branching candidates */
429 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, NULL, &nlpcands, NULL) );
430 assert(nlpcands > 0);
431
432 *result = SCIP_DIDNOTRUN;
433
434 /* Get branching rule data */
435 branchruledata = SCIPbranchruleGetData(branchrule);
436 assert(branchruledata != NULL);
437
438 /* Compute the reliability pseudo-cost branching scores for the candidates */
439 if ( branchruledata->performrelpscost )
440 {
441 /* We do not branch using this rule, but if enabled do take all the bound and conflict inferences made */
442 SCIP_CALL( SCIPexecRelpscostBranching(scip, lpcands, lpcandssol, lpcandsfrac, nlpcands, FALSE, result) );
443 assert(*result == SCIP_DIDNOTRUN || *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM);
444 }
445
446 /* Return SCIP_OKAY if relpscost has shown that this node can be cutoff or some variable domains have changed */
447 if( *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM )
448 {
449 return SCIP_OKAY;
450 }
451
452 /* Get the maximum number of LP branching candidates that we generate cuts for and score */
453 if( branchruledata->maxncands >= 0 )
454 {
455 maxncands = MIN(nlpcands, branchruledata->maxncands);
456 }
457 else
458 {
459 maxncands = nlpcands;
460 }
461
462 /* Get the Column and Row data */
463 SCIP_CALL(SCIPgetLPColsData(scip, &cols, &ncols));
464 SCIP_CALL(SCIPgetLPRowsData(scip, &rows, &nrows));
465
466 /* Allocate temporary memory */
467 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
468 SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
469 SCIP_CALL( SCIPallocBufferArray(scip, &basicvarpos2tableaurow, ncols) );
470 SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
471 SCIP_CALL( SCIPallocBufferArray(scip, &binvarow, ncols) );
472 SCIP_CALL( SCIPallocBufferArray(scip, &inds, nrows) );
473
474 /* Create basis indices mapping (from the column position to LP tableau rox index) */
475 for( i = 0; i < ncols; ++i )
476 {
477 basicvarpos2tableaurow[i] = -1;
478 }
479 SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
480 for( i = 0; i < nrows; ++i )
481 {
482 if( basisind[i] >= 0 )
483 basicvarpos2tableaurow[basisind[i]] = i;
484 }
485
486 /* Initialise the best candidate */
487 bestcand = 0;
488 bestscore = -SCIPinfinity(scip);
489 ninds = -1;
490
491 /* Iterate over candidates and get best cut score */
492 for( i = 0; i < maxncands; i++ )
493 {
494 /* Initialise the score of the cut */
495 score = 0;
496
497 /* Get the LP position of the branching candidate */
498 col = SCIPvarGetCol(lpcands[i]);
499 lppos = SCIPcolGetLPPos(col);
500 assert(lppos != -1);
501
502 /* get the row of B^-1 for this basic integer variable with fractional solution value */
503 SCIP_CALL(SCIPgetLPBInvRow(scip, basicvarpos2tableaurow[lppos], binvrow, inds, &ninds));
504
505 /* Get the Tableau row for this basic integer variable with fractional solution value */
506 SCIP_CALL(SCIPgetLPBInvARow(scip, basicvarpos2tableaurow[lppos], binvrow, binvarow, inds, &ninds));
507
508 /* Compute the GMI cut */
509 success = getGMIFromRow(scip, ncols, nrows, cols, rows, binvrow, binvarow, &lpcandssol[i], cutcoefs,
510 &cutrhs, branchruledata->useweakercuts);
511
512 /* Calculate the weighted sum score of measures */
513 if ( success )
514 {
515 cut = NULL;
517 FALSE, TRUE) );
518 for( j = 0; j < ncols; ++j )
519 {
520 if( !SCIPisZero(scip, cutcoefs[j]) )
521 {
523 cutcoefs[SCIPcolGetLPPos(cols[j])]) );
524 }
525 }
526 assert( SCIPgetCutEfficacy(scip, NULL, cut) >= -SCIPfeastol(scip) );
527 if ( branchruledata-> efficacyweight != 0 )
528 score += branchruledata->efficacyweight * SCIPgetCutEfficacy(scip, NULL, cut);
529 if ( branchruledata->objparallelweight != 0 )
530 score += branchruledata->objparallelweight * SCIPgetRowObjParallelism(scip, cut);
531 if ( branchruledata->intsupportweight != 0 )
532 score += branchruledata->intsupportweight * SCIPgetRowNumIntCols(scip, cut) / (SCIP_Real) SCIProwGetNNonz(cut);
533 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
534
535 /* Replace the best cut if score is higher */
536 if (score > bestscore) {
537 bestscore = score;
538 bestcand = i;
539 }
540 }
541 }
542
543 /* Free temporary memory */
545 SCIPfreeBufferArray(scip, &binvrow);
546 SCIPfreeBufferArray(scip, &binvarow);
547 SCIPfreeBufferArray(scip, &basicvarpos2tableaurow);
548 SCIPfreeBufferArray(scip, &basisind);
549 SCIPfreeBufferArray(scip, &cutcoefs);
550
551 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (frac=%g, factor=%g, score=%g)\n",
552 nlpcands, bestcand, SCIPvarGetName(lpcands[bestcand]), lpcandsfrac[bestcand],
553 SCIPvarGetBranchFactor(lpcands[bestcand]), bestscore);
554
555 /* Perform the branching */
556 SCIP_CALL( SCIPbranchVar(scip, lpcands[bestcand], NULL, NULL, NULL) );
557 *result = SCIP_BRANCHED;
558
559 return SCIP_OKAY;
560}
561
562
563/*
564 * branching rule specific interface methods
565 */
566
567/** creates the Gomory cut branching rule and includes it in SCIP */
569 SCIP* scip /**< SCIP data structure */
570 )
571{
572 SCIP_BRANCHRULEDATA* branchruledata;
573 SCIP_BRANCHRULE* branchrule;
574
575 /* create branching rule data */
576 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
577
578 /* include branching rule */
581
582 assert(branchrule != NULL);
583
584 /* set non-fundamental callbacks via specific setter functions*/
585 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyGomory) );
586 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeGomory) );
587 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpGomory) );
588
589 /* Gomory cut branching rule parameters */
590 SCIP_CALL( SCIPaddIntParam(scip,"branching/gomory/maxncands",
591 "maximum amount of branching candidates to generate Gomory cuts for (-1: all candidates)",
592 &branchruledata->maxncands, FALSE, DEFAULT_MAXNCANDS, -1, INT_MAX, NULL, NULL) );
593 SCIP_CALL( SCIPaddRealParam(scip,"branching/gomory/efficacyweight",
594 "weight of efficacy in the weighted sum cut scoring rule",
595 &branchruledata->efficacyweight, FALSE, DEFAULT_EFFICACYWEIGHT, -1.0, 1.0, NULL, NULL) );
596 SCIP_CALL( SCIPaddRealParam(scip,"branching/gomory/objparallelweight",
597 "weight of objective parallelism in the weighted sum cut scoring rule",
598 &branchruledata->objparallelweight, FALSE, DEFAULT_OBJPARALLELWEIGHT, -1.0, 1.0, NULL, NULL) );
599 SCIP_CALL( SCIPaddRealParam(scip,"branching/gomory/intsupportweight",
600 "weight of integer support in the weighted sum cut scoring rule",
601 &branchruledata->intsupportweight, FALSE, DEFAULT_INTSUPPORTWEIGHT, -1.0, 1.0, NULL, NULL) );
602 SCIP_CALL( SCIPaddBoolParam(scip,"branching/gomory/performrelpscost",
603 "whether relpscost branching should be called without branching (used for bound inferences and conflicts)",
604 &branchruledata->performrelpscost, FALSE, DEFAULT_PERFORMRELPSCOST, NULL, NULL) );
605 SCIP_CALL( SCIPaddBoolParam(scip,"branching/gomory/useweakercuts",
606 "use weaker cuts that are exactly derived from the branching split disjunction",
607 &branchruledata->useweakercuts, FALSE, DEFAULT_USEWEAKERCUTS, NULL, NULL) );
608
609 return SCIP_OKAY;
610}
#define BRANCHRULE_DESC
Definition: branch_gomory.c:74
static SCIP_DECL_BRANCHFREE(branchFreeGomory)
#define BRANCHRULE_PRIORITY
Definition: branch_gomory.c:75
#define DEFAULT_EFFICACYWEIGHT
Definition: branch_gomory.c:80
#define BRANCHRULE_NAME
Definition: branch_gomory.c:73
static SCIP_DECL_BRANCHCOPY(branchCopyGomory)
#define DEFAULT_OBJPARALLELWEIGHT
Definition: branch_gomory.c:81
static SCIP_Bool getGMIFromRow(SCIP *scip, int ncols, int nrows, SCIP_COL **cols, SCIP_ROW **rows, const SCIP_Real *binvrow, const SCIP_Real *binvarow, const SCIP_Real *lpval, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, SCIP_Bool useweakerscuts)
static SCIP_DECL_BRANCHEXECLP(branchExeclpGomory)
#define DEFAULT_PERFORMRELPSCOST
Definition: branch_gomory.c:83
#define BRANCHRULE_MAXDEPTH
Definition: branch_gomory.c:76
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_gomory.c:77
#define DEFAULT_USEWEAKERCUTS
Definition: branch_gomory.c:84
#define DEFAULT_INTSUPPORTWEIGHT
Definition: branch_gomory.c:82
#define DEFAULT_MAXNCANDS
Definition: branch_gomory.c:79
Gomory cut branching rule.
reliable pseudo costs branching rule
#define NULL
Definition: def.h:267
#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_RETCODE SCIPexecRelpscostBranching(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result)
SCIP_RETCODE SCIPincludeBranchruleGomory(SCIP *scip)
#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
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:116
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1050
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:17093
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:17072
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:16963
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:16973
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:17031
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:94
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_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:785
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
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 SCIPfreeBlockMemoryNull(scip, ptr)
Definition: scip_mem.h:109
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:17391
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17411
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17238
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:17227
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17501
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 SCIPcreateEmptyRowUnspec(SCIP *scip, SCIP_ROW **row, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1482
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17258
SCIP_Real SCIPgetRowObjParallelism(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2190
int SCIPgetRowNumIntCols(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1886
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17248
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:17340
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17789
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetBranchFactor(SCIP_VAR *var)
Definition: var.c:18238
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
public methods for branching rules
public methods for LP management
public methods for message output
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
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 the branch-and-bound tree
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:57
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_BASESTAT_BASIC
Definition: type_lpi.h:92
@ SCIP_BASESTAT_UPPER
Definition: type_lpi.h:93
@ SCIP_BASESTAT_LOWER
Definition: type_lpi.h:91
enum SCIP_BaseStat SCIP_BASESTAT
Definition: type_lpi.h:96
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_BRANCHED
Definition: type_result.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63