branch_gomory.c File Reference

Detailed Description

Gomory cut branching rule.

Author

Mark Turner

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 void	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 void 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

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(), and SCIProwIsModifiable().

Referenced by SCIP_DECL_BRANCHEXECLP().

SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyGomory  )

static

copy method for branchrule plugins (called when SCIP copies plugins)

Definition at line 347 of file branch_gomory.c.

References BRANCHRULE_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetName(), and SCIPincludeBranchruleGomory().

SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeGomory  )

static

destructor of branching rule to free user data (called when SCIP is exiting)

Definition at line 362 of file branch_gomory.c.

References NULL, SCIP_OKAY, SCIPbranchruleGetData(), and SCIPfreeBlockMemoryNull.

SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpGomory  )

static

branching execution method for fractional LP solutions

Definition at line 378 of file branch_gomory.c.

References BRANCHRULE_NAME, FALSE, getGMIFromRow(), MIN, NULL, 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.