Detailed Description

Branching rules based on the Single-Variable-Branching (SVB) model.

Author: Daniel Anderson; Pierre Le Bodic

The Single-Variable-Branching (SVB) model is a simplified model of Branch & Bound trees, from which several nontrivial variable selection rules arise. The Treemodel branching rule complements SCIP's hybrid branching by suggesting improved branching variables given the current pseudocosts and the current dual gap.

Given a variable with dual bound changes (l, r) (both positive) and an absolute gap G, the SVB model describes the tree that needs to be built by branching on that same variable at every node until the value G is reached at every leaf, starting from 0 at the root node. If we do so for every variable, we can select the variable that produces the smallest tree. In the case where the gap is not known, then we can compute the growth rate of the tree, which we call the ratio. The ratio of a variable (l, r) is the factor by which the size of the tree built using (l, r) that closes a gap G must be multiplied by to close a gap G+1. This ratio is not constant for all gaps, but when G tends to infinity, it converges to a fixed value we can compute numerically using a root finding algorithm (e.g. Laguerre). The ratio is used when the gap is too large (e.g. no primal bound known) or to help approximate the size of the SVB tree for that variable.

See the following publication for more detail:

: Pierre Le Bodic and George Nemhauser
An abstract model for branching and its application to mixed integer programming
Mathematical Programming, 2017

Definition in file treemodel.c.

#include "scip/treemodel.h"
#include "scip/history.h"
#include "scip/var.h"
#include <limits.h>

Go to the source code of this file.

Data Structures
struct	SCIP_Treemodel

struct	SCIP_Ratio

Macros
#define	LAGUERRE_THRESHOLD 100

#define	DEFAULT_ENABLE FALSE

#define	DEFAULT_HIGHRULE 'r'

#define	DEFAULT_LOWRULE 'r'

#define	DEFAULT_HEIGHT 10

#define	DEFAULT_FILTERHIGH 'a'

#define	DEFAULT_FILTERLOW 'a'

#define	DEFAULT_MAXFPITER 24

#define	DEFAULT_MAXSVTSHEIGHT 100

#define	DEFAULT_FALLBACKINF 'r'

#define	DEFAULT_FALLBACKNOPRIM 'r'

#define	DEFAULT_SMALLPSCOST 0.1

Typedefs
typedef struct SCIP_Ratio	SCIP_RATIO

Functions
static	SCIP_DECL_SORTINDCOMP (sciprealcomp)

static SCIP_RETCODE	findNonDominatedVars (SCIP scip, SCIP_Real a, SCIP_Real b, int size, int ndominated, SCIP_Bool *dominated)

static SCIP_Bool	hasBetterRatio (SCIP scip, SCIP_RATIO branchratio, SCIP_Real leftgain, SCIP_Real rightgain)

static void	computeVarRatio (SCIP scip, SCIP_TREEMODEL treemodel, SCIP_VAR var, SCIP_Real leftgain, SCIP_Real rightgain, SCIP_RATIO branchratio)

static SCIP_RETCODE	selectCandidateUsingRatio (SCIP scip, SCIP_TREEMODEL treemodel, SCIP_VAR *branchcands, SCIP_Real mingains, SCIP_Real maxgains, SCIP_Bool filterdominated, SCIP_Bool dominated, int nbranchcands, int *bestcand)

static SCIP_Real	computeSVTS (SCIP scip, SCIP_TREEMODEL treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real mingain, SCIP_Real maxgain)

static SCIP_RETCODE	selectCandidateUsingSVTS (SCIP scip, SCIP_TREEMODEL treemodel, SCIP_VAR *branchcands, SCIP_Real mingains, SCIP_Real maxgains, SCIP_Real tiebreakerscore, SCIP_Real localabsgap, SCIP_Bool filterdominated, SCIP_Bool dominated, int nbranchcands, int ndominated, int bestcand)

static SCIP_Real	integerpow (SCIP_Real a, int b)

static SCIP_Real	computeSampleTreesize (SCIP scip, SCIP_TREEMODEL treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real leftgain, SCIP_Real rightgain)

static SCIP_RETCODE	selectCandidateUsingSampling (SCIP scip, SCIP_TREEMODEL treemodel, SCIP_VAR *branchcands, SCIP_Real mingains, SCIP_Real maxgains, SCIP_Real tiebreakerscore, SCIP_Real localabsgap, SCIP_Bool filterdominated, SCIP_Bool dominated, int nbranchcands, int ndominated, int bestcand)

SCIP_RETCODE	SCIPtreemodelInit (SCIP scip, SCIP_TREEMODEL *treemodel)

SCIP_RETCODE	SCIPtreemodelFree (SCIP scip, SCIP_TREEMODEL *treemodel)

SCIP_Bool	SCIPtreemodelIsEnabled (SCIP scip, SCIP_TREEMODEL treemodel)

SCIP_RETCODE	SCIPtreemodelSelectCandidate (SCIP scip, SCIP_TREEMODEL treemodel, SCIP_VAR *branchcands, SCIP_Real mingains, SCIP_Real maxgains, SCIP_Real tiebreakerscore, int nbranchcands, int *bestcand)

Macro Definition Documentation

◆ LAGUERRE_THRESHOLD

#define LAGUERRE_THRESHOLD 100

Maximum value of r/l at which Laguerre is the prefered FP method

Definition at line 60 of file treemodel.c.

Referenced by computeVarRatio().

◆ DEFAULT_ENABLE

#define DEFAULT_ENABLE FALSE

should candidate branching variables be scored using the Treemodel rule?

Definition at line 63 of file treemodel.c.

◆ DEFAULT_HIGHRULE

#define DEFAULT_HIGHRULE 'r'

scoring function to use at nodes predicted to be high in the tree. ('d'efault, 's'vts, 'r'atio, 't'ree sample)

Definition at line 64 of file treemodel.c.

◆ DEFAULT_LOWRULE

#define DEFAULT_LOWRULE 'r'

scoring function to use at nodes predicted to be low in the tree ('d'efault, 's'vts, 'r'atio, 't'ree sample)

Definition at line 67 of file treemodel.c.

◆ DEFAULT_HEIGHT

#define DEFAULT_HEIGHT 10

estimated tree height at which we switch from using the low rule to the high rule

Definition at line 70 of file treemodel.c.

◆ DEFAULT_FILTERHIGH

#define DEFAULT_FILTERHIGH 'a'

should dominated candidates be filtered before using the high scoring function? ('a'uto, 't'rue, 'f'alse)

Definition at line 73 of file treemodel.c.

◆ DEFAULT_FILTERLOW

#define DEFAULT_FILTERLOW 'a'

should dominated candidates be filtered before using the low scoring function? ('a'uto, 't'rue, 'f'alse)

Definition at line 76 of file treemodel.c.

◆ DEFAULT_MAXFPITER

#define DEFAULT_MAXFPITER 24

maximum number of fixed-point iterations when computing the ratio

Definition at line 79 of file treemodel.c.

◆ DEFAULT_MAXSVTSHEIGHT

#define DEFAULT_MAXSVTSHEIGHT 100

maximum height to compute the SVTS score exactly before approximating

Definition at line 80 of file treemodel.c.

◆ DEFAULT_FALLBACKINF

#define DEFAULT_FALLBACKINF 'r'

which method should be used as a fallback if the tree size estimates are infinite? ('d'efault, 'r'atio)

Definition at line 81 of file treemodel.c.

◆ DEFAULT_FALLBACKNOPRIM

#define DEFAULT_FALLBACKNOPRIM 'r'

which method should be used as a fallback if there is no primal bound available? ('d'efault, 'r'atio)

Definition at line 84 of file treemodel.c.

◆ DEFAULT_SMALLPSCOST

#define DEFAULT_SMALLPSCOST 0.1

threshold at which pseudocosts are considered small, making hybrid scores more likely to be the deciding factor in branching

Definition at line 87 of file treemodel.c.

Typedef Documentation

◆ SCIP_RATIO

typedef struct SCIP_Ratio SCIP_RATIO

Definition at line 132 of file treemodel.c.

Function Documentation

◆ SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( sciprealcomp )

static

a comparison method for the next method. It simply compares two SCIP_Real

Definition at line 136 of file treemodel.c.

◆ findNonDominatedVars()

static SCIP_RETCODE findNonDominatedVars	(	SCIP *	scip,
		SCIP_Real *	a,
		SCIP_Real *	b,
		int	size,
		int *	ndominated,
		SCIP_Bool *	dominated
	)

static

given a pair of arrays of real non-negative values (a,b), with a <= b, computes the pairs that belong to the pareto front (with a tolerance). In other words, we are looking for non-dominated pairs of values. One value and one array are computed after this method. The value is the number of non-dominated elements. The array is a boolean array that indicates if an element is dominated. In case of a draw, only one variable is considered as non-dominated.

Parameters

scip	SCIP data structure
a	the first set of values
b	the second set of values
size	the size of array a (and b)
ndominated	returns the number of dominated elements
dominated	returns the array of booleans that determine if an element is dominated

Definition at line 162 of file treemodel.c.

References FALSE, hasBetterRatio(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGT(), SCIPisLT(), SCIPsortDownInd(), and TRUE.

Referenced by SCIPtreemodelSelectCandidate().

◆ hasBetterRatio()

static SCIP_Bool hasBetterRatio	(	SCIP *	scip,
		SCIP_RATIO *	branchratio,
		SCIP_Real	leftgain,
		SCIP_Real	rightgain
	)

static

returns true iff the variable with given gains has a ratio better (i.e smaller) than the given one

Parameters

scip	SCIP data structure
branchratio	The variable's ratio to compare against
leftgain	the left gain of a variable
rightgain	the right gain of a variable

Definition at line 296 of file treemodel.c.

Referenced by findNonDominatedVars(), and selectCandidateUsingRatio().

◆ computeVarRatio()

static void computeVarRatio	(	SCIP *	scip,
		SCIP_TREEMODEL *	treemodel,
		SCIP_VAR *	var,
		SCIP_Real	leftgain,
		SCIP_Real	rightgain,
		SCIP_RATIO *	branchratio
	)

static

computes the variable ratio corresponding to the left and right gains

Parameters

scip	SCIP data structure
treemodel	Treemodel parameter data structure
var	the candidate branching variable
leftgain	the left gain of the variable
rightgain	the right gain of the variable
branchratio	storage for the computed ratio

Definition at line 321 of file treemodel.c.

References a, FALSE, SCIP_Var::history, SCIP_Ratio::invleft, LAGUERRE_THRESHOLD, SCIP_Treemodel::maxfpiter, pow(), r, SCIP_Bool, SCIP_Real, SCIPhistoryGetLastBalance(), SCIPhistoryGetLastRatio(), SCIPhistoryIsRatioValid(), SCIPhistorySetRatioHistory(), SCIPisEQ(), SCIPisGE(), SCIPisSumEQ(), SCIPisZero(), selectCandidateUsingRatio(), sqrt(), TRUE, SCIP_Ratio::upratio, and SCIP_Ratio::valid.

Referenced by computeSampleTreesize(), computeSVTS(), and selectCandidateUsingRatio().

◆ selectCandidateUsingRatio()

static SCIP_RETCODE selectCandidateUsingRatio	(	SCIP *	scip,
		SCIP_TREEMODEL *	treemodel,
		SCIP_VAR **	branchcands,
		SCIP_Real *	mingains,
		SCIP_Real *	maxgains,
		SCIP_Bool	filterdominated,
		SCIP_Bool *	dominated,
		int	nbranchcands,
		int *	bestcand
	)

static

use the Ratio scoring function to select a branching candidate

Parameters

scip	SCIP data structure
treemodel	Treemodel parameter data structure
branchcands	branching candidate storage
mingains	minimum gain of rounding downwards or upwards
maxgains	maximum gain of rounding downwards or upwards
filterdominated	whether dominated variables have been filtered
dominated	whether each variable is dominated or not
nbranchcands	the number of branching candidates
bestcand	the best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 445 of file treemodel.c.

References computeSVTS(), computeVarRatio(), hasBetterRatio(), SCIP_OKAY, SCIP_Real, and SCIP_Ratio::valid.

Referenced by computeVarRatio(), SCIPtreemodelSelectCandidate(), selectCandidateUsingSampling(), and selectCandidateUsingSVTS().

◆ computeSVTS()

static SCIP_Real computeSVTS	(	SCIP *	scip,
		SCIP_TREEMODEL *	treemodel,
		SCIP_VAR *	var,
		SCIP_Real	absgap,
		SCIP_Real	mingain,
		SCIP_Real	maxgain
	)

static

Returns the predicted treesize for the gap and given up and down gains

Parameters

scip	SCIP data structure
treemodel	Treemodel parameter data structure
var	the candidate branching variable
absgap	the absolute gap to close (typically the local gap at the current node)
mingain	prediction of smaller objective gain of downwards/upwards
maxgain	prediction of larger objective gain of downwards/upwards

Definition at line 489 of file treemodel.c.

References computeVarRatio(), SCIP_Ratio::invleft, SCIP_Treemodel::maxsvtsheight, pow(), SCIP_Real, SCIP_REAL_MAX, SCIPceil(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), selectCandidateUsingSVTS(), SCIP_Ratio::upratio, and SCIP_Ratio::valid.

Referenced by selectCandidateUsingRatio(), and selectCandidateUsingSVTS().

◆ selectCandidateUsingSVTS()

static SCIP_RETCODE selectCandidateUsingSVTS	(	SCIP *	scip,
		SCIP_TREEMODEL *	treemodel,
		SCIP_VAR **	branchcands,
		SCIP_Real *	mingains,
		SCIP_Real *	maxgains,
		SCIP_Real *	tiebreakerscore,
		SCIP_Real	localabsgap,
		SCIP_Bool	filterdominated,
		SCIP_Bool *	dominated,
		int	nbranchcands,
		int	ndominated,
		int *	bestcand
	)

static

use the SVTS scoring function to select a branching candidate

Parameters

scip	SCIP data structure
treemodel	Treemodel parameter data structure
branchcands	branching candidate storage
mingains	minimum gain of rounding downwards or upwards
maxgains	maximum gain of rounding downwards or upwards
tiebreakerscore	scores to use for tie breaking
localabsgap	The dual gap at the current node
filterdominated	whether dominated variables have been filtered
dominated	whether each variable is dominated or not
nbranchcands	the number of branching candidates
ndominated	the number of dominated candidates
bestcand	the best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 575 of file treemodel.c.

References a, b, computeSVTS(), SCIP_Treemodel::fallbackinf, SCIP_Treemodel::fallbacknoprim, integerpow(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), and selectCandidateUsingRatio().

Referenced by computeSVTS(), and SCIPtreemodelSelectCandidate().

◆ integerpow()

static SCIP_Real integerpow	(	SCIP_Real	a,
		int	b
	)

static

computes a^b for integer b

Parameters

a	the base
b	the integer exponent

Definition at line 666 of file treemodel.c.

References a, computeSampleTreesize(), and SCIP_Real.

Referenced by computeSampleTreesize(), and selectCandidateUsingSVTS().

◆ computeSampleTreesize()

static SCIP_Real computeSampleTreesize	(	SCIP *	scip,
		SCIP_TREEMODEL *	treemodel,
		SCIP_VAR *	var,
		SCIP_Real	absgap,
		SCIP_Real	leftgain,
		SCIP_Real	rightgain
	)

static

returns the sampled tree size for the given lp gains and dual gap

Parameters

scip	SCIP data structure
treemodel	Treemodel parameter data structure
var	the candidate branching variable
absgap	the absolute gap to close (typically the local at the current node)
leftgain	The minimum gain from branching on this variable
rightgain	The maximum gain from branching on this variable

Definition at line 685 of file treemodel.c.

References computeVarRatio(), integerpow(), SCIP_Ratio::invleft, pow(), SCIP_Real, SCIP_REAL_MAX, selectCandidateUsingSampling(), SCIP_Ratio::upratio, and SCIP_Ratio::valid.

Referenced by integerpow(), and selectCandidateUsingSampling().

◆ selectCandidateUsingSampling()

static SCIP_RETCODE selectCandidateUsingSampling	(	SCIP *	scip,
		SCIP_TREEMODEL *	treemodel,
		SCIP_VAR **	branchcands,
		SCIP_Real *	mingains,
		SCIP_Real *	maxgains,
		SCIP_Real *	tiebreakerscore,
		SCIP_Real	localabsgap,
		SCIP_Bool	filterdominated,
		SCIP_Bool *	dominated,
		int	nbranchcands,
		int	ndominated,
		int *	bestcand
	)

static

use the Tree Sampling scoring function to select a branching candidate

Parameters

scip	SCIP data structure
treemodel	Treemodel parameter data structure
branchcands	branching candidate storage
mingains	minimum gain of rounding downwards or upwards
maxgains	maximum gain of rounding downwards or upwards
tiebreakerscore	scores to use for tie breaking
localabsgap	The dual gap at the current node
filterdominated	whether dominated variables have been filtered
dominated	whether each variable is dominated or not
nbranchcands	the number of branching candidates
ndominated	the number of dominated candidates
bestcand	the best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 734 of file treemodel.c.

References computeSampleTreesize(), SCIP_Treemodel::fallbackinf, SCIP_Treemodel::fallbacknoprim, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), SCIPtreemodelInit(), and selectCandidateUsingRatio().

Referenced by computeSampleTreesize(), and SCIPtreemodelSelectCandidate().

◆ SCIPtreemodelInit()

SCIP_RETCODE SCIPtreemodelInit	(	SCIP *	scip,
		SCIP_TREEMODEL **	treemodel
	)

initialises the Treemodel parameter data structure

Parameters

scip	SCIP data structure
treemodel	Treemodel parameter data structure

Definition at line 825 of file treemodel.c.

Referenced by selectCandidateUsingSampling().

◆ SCIPtreemodelFree()

SCIP_RETCODE SCIPtreemodelFree	(	SCIP *	scip,
		SCIP_TREEMODEL **	treemodel
	)

frees the Treemodel parameter data structure

Parameters

scip	SCIP data structure
treemodel	Treemodel parameter data structure

Definition at line 883 of file treemodel.c.

◆ SCIPtreemodelIsEnabled()

SCIP_Bool SCIPtreemodelIsEnabled	(	SCIP *	scip,
		SCIP_TREEMODEL *	treemodel
	)

returns TRUE if the Treemodel branching rules are enabled

Parameters

scip	SCIP data structure
treemodel	Treemodel parameter data structure

Definition at line 899 of file treemodel.c.

Referenced by execRelpscost().

◆ SCIPtreemodelSelectCandidate()

SCIP_RETCODE SCIPtreemodelSelectCandidate	(	SCIP *	scip,
		SCIP_TREEMODEL *	treemodel,
		SCIP_VAR **	branchcands,
		SCIP_Real *	mingains,
		SCIP_Real *	maxgains,
		SCIP_Real *	tiebreakerscore,
		int	nbranchcands,
		int *	bestcand
	)

apply the Treemodel branching rules to attempt to select a better branching candidate than the one selected by pseudocost branching

Parameters

scip	SCIP data structure
treemodel	Treemodel parameter data structure
branchcands	branching candidate storage
mingains	minimum gain of rounding downwards or upwards
maxgains	maximum gain of rounding downwards or upwards
tiebreakerscore	scores to use for tie breaking
nbranchcands	the number of branching candidates
bestcand	the best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 910 of file treemodel.c.

References SCIP_Treemodel::enabled, SCIP_Treemodel::filterhigh, SCIP_Treemodel::filterlow, findNonDominatedVars(), SCIP_Treemodel::height, SCIP_Treemodel::highrule, SCIP_Treemodel::lowrule, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetNodeLowerbound(), SCIPgetUpperbound(), SCIPinfinity(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), selectCandidateUsingRatio(), selectCandidateUsingSampling(), and selectCandidateUsingSVTS().

Referenced by execRelpscost().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ LAGUERRE_THRESHOLD

◆ DEFAULT_ENABLE

◆ DEFAULT_HIGHRULE

◆ DEFAULT_LOWRULE

◆ DEFAULT_HEIGHT

◆ DEFAULT_FILTERHIGH

◆ DEFAULT_FILTERLOW

◆ DEFAULT_MAXFPITER

◆ DEFAULT_MAXSVTSHEIGHT

◆ DEFAULT_FALLBACKINF

◆ DEFAULT_FALLBACKNOPRIM

◆ DEFAULT_SMALLPSCOST

Typedef Documentation

◆ SCIP_RATIO

Function Documentation

◆ SCIP_DECL_SORTINDCOMP()

◆ findNonDominatedVars()

◆ hasBetterRatio()

◆ computeVarRatio()

◆ selectCandidateUsingRatio()

◆ computeSVTS()

◆ selectCandidateUsingSVTS()

◆ integerpow()

◆ computeSampleTreesize()

◆ selectCandidateUsingSampling()

◆ SCIPtreemodelInit()

◆ SCIPtreemodelFree()

◆ SCIPtreemodelIsEnabled()

◆ SCIPtreemodelSelectCandidate()