Scippy

SCIP

Solving Constraint Integer Programs

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

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
scipSCIP data structure
ncolsNumber of columns (original variables) in the LP
nrowsNumber of rows (slack variables) in the LP
colsColumn data of the LP
rowsRow data of the LP
binvrowrow of B^-1 for current basic variable
binvarowrow of B^-1A for current basic variable
lpvalvalue of variable at current LP solution
cutcoefsarray to store cut coefficients
cutrhspointer to store rhs of cut
useweakerscutsuse 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 SCIP_DECL_BRANCHCOPY ( branchCopyGomory  )
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 SCIP_DECL_BRANCHFREE ( branchFreeGomory  )
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()