SCIP
Solving Constraint Integer Programs
branch_gomory.c File Reference
Detailed Description
Gomory cut branching rule.
The approach is based on the following papers.
M. Turner, T. Berthold, M. Besancon, T. Koch
Branching via Cutting Plane Selection: Improving Hybrid Branching,
arXiv preprint arXiv:2306.06050
The Gomory cut branching rule selects a candidate integer variable $j$ with a fractional solution value. Each candidate variable must be a basic variable in the LP Tableau (if not then it would have to be at its bound that is integer-valued) This branching rule calculates the GMI cut for the aggregated row of the LP tableau associated with the candidate variable. The generated cut is then scored using a weighted sum rule. The branching candidate whose cut is highest scoring is then selected. For more details on the method, see:
- Mark Turner, Timo Berthold, Mathieu Besançon, Thorsten Koch
Branching via Cutting Plane Selection: Improving Hybrid Branching
2023
Definition in file branch_gomory.c.
#include "scip/branch_gomory.h"#include "scip/pub_branch.h"#include "scip/pub_var.h"#include "scip/pub_lp.h"#include "scip/pub_tree.h"#include "scip/pub_message.h"#include "scip/scip_branch.h"#include "scip/scip_cut.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_numerics.h"#include "scip/scip_lp.h"#include "scip/scip_tree.h"#include "scip/scip_param.h"#include "scip/branch_relpscost.h"#include <string.h>#include <assert.h>Go to the source code of this file.
Macros | |
| #define | BRANCHRULE_NAME "gomory" |
| #define | BRANCHRULE_DESC "Gomory cut score branching" |
| #define | BRANCHRULE_PRIORITY -1000 |
| #define | BRANCHRULE_MAXDEPTH -1 |
| #define | BRANCHRULE_MAXBOUNDDIST 1.0 |
| #define | DEFAULT_MAXNCANDS -1 |
| #define | DEFAULT_EFFICACYWEIGHT 1.0 |
| #define | DEFAULT_OBJPARALLELWEIGHT 0.0 |
| #define | DEFAULT_INTSUPPORTWEIGHT 0.0 |
| #define | DEFAULT_PERFORMRELPSCOST FALSE |
| #define | DEFAULT_USEWEAKERCUTS TRUE |
Functions | |
| 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_BRANCHCOPY (branchCopyGomory) |
| static | SCIP_DECL_BRANCHFREE (branchFreeGomory) |
| static | SCIP_DECL_BRANCHEXECLP (branchExeclpGomory) |
| SCIP_RETCODE | SCIPincludeBranchruleGomory (SCIP *scip) |
Macro Definition Documentation
◆ BRANCHRULE_NAME
| #define BRANCHRULE_NAME "gomory" |
Definition at line 73 of file branch_gomory.c.
◆ BRANCHRULE_DESC
| #define BRANCHRULE_DESC "Gomory cut score branching" |
Definition at line 74 of file branch_gomory.c.
◆ BRANCHRULE_PRIORITY
| #define BRANCHRULE_PRIORITY -1000 |
Definition at line 75 of file branch_gomory.c.
◆ BRANCHRULE_MAXDEPTH
| #define BRANCHRULE_MAXDEPTH -1 |
Definition at line 76 of file branch_gomory.c.
◆ BRANCHRULE_MAXBOUNDDIST
| #define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 77 of file branch_gomory.c.
◆ DEFAULT_MAXNCANDS
| #define DEFAULT_MAXNCANDS -1 |
maximum number of branching candidates to produce a cut for
Definition at line 79 of file branch_gomory.c.
◆ DEFAULT_EFFICACYWEIGHT
| #define DEFAULT_EFFICACYWEIGHT 1.0 |
the weight of efficacy in weighted sum cut scoring rule
Definition at line 80 of file branch_gomory.c.
◆ DEFAULT_OBJPARALLELWEIGHT
| #define DEFAULT_OBJPARALLELWEIGHT 0.0 |
the weight of objective parallelism in weighted sum scoring rule
Definition at line 81 of file branch_gomory.c.
◆ DEFAULT_INTSUPPORTWEIGHT
| #define DEFAULT_INTSUPPORTWEIGHT 0.0 |
the weight of integer support in weighted sum cut scoring rule
Definition at line 82 of file branch_gomory.c.
◆ DEFAULT_PERFORMRELPSCOST
| #define DEFAULT_PERFORMRELPSCOST FALSE |
if relpscost branching should be called without actual branching
Definition at line 83 of file branch_gomory.c.
◆ DEFAULT_USEWEAKERCUTS
| #define DEFAULT_USEWEAKERCUTS TRUE |
use weaker cuts derived from the exact branching split
Definition at line 84 of file branch_gomory.c.
Function Documentation
◆ getGMIFromRow()
|
static |
Generate GMI cut: The GMI is given by sum(f_j x_j , j in J_I s.t. f_j <= f_0) + sum((1-f_j)*f_0/(1 - f_0) x_j, j in J_I s.t. f_j > f_0) + sum(a_j x_j, , j in J_C s.t. a_j >= 0) - sum(a_j*f_0/(1-f_0) x_j , j in J_C s.t. a_j < 0) >= f_0. where J_I are the integer non-basic variables and J_C are the continuous. f_0 is the fractional part of lpval a_j is the j-th coefficient of the tableau row and f_j its fractional part Note: we create -% <= -f_0 !! Note: this formula is valid for a problem of the form Ax = b, x>= 0. Since we do not have such problem structure in general, we have to (implicitly) transform whatever we are given to that form. Specifically, non-basic variables at their lower bound are shifted so that the lower bound is 0 and non-basic at their upper bound are complemented.
- Parameters
-
scip SCIP data structure ncols Number of columns (original variables) in the LP nrows Number of rows (slack variables) in the LP cols Column data of the LP rows Row data of the LP binvrow row of B^-1 for current basic variable binvarow row of B^-1A for current basic variable lpval value of variable at current LP solution cutcoefs array to store cut coefficients cutrhs pointer to store rhs of cut useweakerscuts use weakener cuts derived from the exact branching split
Definition at line 121 of file branch_gomory.c.
References BMSclearMemoryArray, NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_Real, SCIPcolGetBasisStatus(), SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetUb(), SCIPcolIsIntegral(), SCIPfeasFrac(), SCIPfrac(), SCIPgetRowActivity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsIntegral(), SCIProwIsModifiable(), and TRUE.
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ SCIP_DECL_BRANCHCOPY()
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 349 of file branch_gomory.c.
References BRANCHRULE_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetName(), and SCIPincludeBranchruleGomory().
◆ SCIP_DECL_BRANCHFREE()
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 364 of file branch_gomory.c.
References NULL, SCIP_OKAY, SCIPbranchruleGetData(), and SCIPfreeBlockMemoryNull.
◆ SCIP_DECL_BRANCHEXECLP()
|
static |
branching execution method for fractional LP solutions
Definition at line 380 of file branch_gomory.c.
References BRANCHRULE_NAME, FALSE, getGMIFromRow(), MIN, NULL, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPaddVarToRow(), SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPbranchVar(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPcreateEmptyRowUnspec(), SCIPdebugMsg, SCIPexecRelpscostBranching(), SCIPfeastol(), SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetCutEfficacy(), SCIPgetLPBasisInd(), SCIPgetLPBInvARow(), SCIPgetLPBInvRow(), SCIPgetLPBranchCands(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetRowNumIntCols(), SCIPgetRowObjParallelism(), SCIPinfinity(), SCIPisZero(), SCIPnodeGetNumber(), SCIPreleaseRow(), SCIProwGetNNonz(), SCIPvarGetBranchFactor(), SCIPvarGetCol(), SCIPvarGetName(), and TRUE.