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:
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) |
#define BRANCHRULE_NAME "gomory" |
Definition at line 73 of file branch_gomory.c.
#define BRANCHRULE_DESC "Gomory cut score branching" |
Definition at line 74 of file branch_gomory.c.
#define BRANCHRULE_PRIORITY -1000 |
Definition at line 75 of file branch_gomory.c.
#define BRANCHRULE_MAXDEPTH -1 |
Definition at line 76 of file branch_gomory.c.
#define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 77 of file branch_gomory.c.
#define DEFAULT_MAXNCANDS -1 |
maximum number of branching candidates to produce a cut for
Definition at line 79 of file branch_gomory.c.
Referenced by SCIPincludeBranchruleGomory(), and SCIPincludeBranchruleLookahead().
#define DEFAULT_EFFICACYWEIGHT 1.0 |
the weight of efficacy in weighted sum cut scoring rule
Definition at line 80 of file branch_gomory.c.
Referenced by SCIPincludeBranchruleGomory(), SCIPincludeCutselDynamic(), SCIPincludeCutselEnsemble(), SCIPincludeCutselHybrid(), SCIPincludeSepaRlt(), and SCIPincludeSepaZerohalf().
#define DEFAULT_OBJPARALLELWEIGHT 0.0 |
the weight of objective parallelism in weighted sum scoring rule
Definition at line 81 of file branch_gomory.c.
Referenced by SCIPincludeBranchruleGomory().
#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.
Referenced by SCIPincludeBranchruleGomory(), SCIPincludeCutselDynamic(), SCIPincludeCutselEnsemble(), and SCIPincludeCutselHybrid().
#define DEFAULT_PERFORMRELPSCOST FALSE |
if relpscost branching should be called without actual branching
Definition at line 83 of file branch_gomory.c.
Referenced by SCIPincludeBranchruleGomory().
#define DEFAULT_USEWEAKERCUTS TRUE |
use weaker cuts derived from the exact branching split
Definition at line 84 of file branch_gomory.c.
Referenced by SCIPincludeBranchruleGomory().
|
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.
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 assert(), BMSclearMemoryArray, c, i, NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_Bool, 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().
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 349 of file branch_gomory.c.
References assert(), BRANCHRULE_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetName(), and SCIPincludeBranchruleGomory().
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 364 of file branch_gomory.c.
References assert(), NULL, SCIP_OKAY, SCIPbranchruleGetData(), and SCIPfreeBlockMemoryNull.
|
static |
branching execution method for fractional LP solutions
Definition at line 380 of file branch_gomory.c.
References assert(), bestcand, BRANCHRULE_NAME, FALSE, getGMIFromRow(), i, lpcands, lpcandsfrac, lpcandssol, MIN, nlpcands, NULL, result, 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.