Detailed Description
Branching rules based on the Single-Variable-Branching (SVB) model.
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.
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 69 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 72 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 73 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 76 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 79 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 82 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 85 of file treemodel.c.
◆ DEFAULT_MAXFPITER
#define DEFAULT_MAXFPITER 24 |
maximum number of fixed-point iterations when computing the ratio
Definition at line 88 of file treemodel.c.
◆ DEFAULT_MAXSVTSHEIGHT
#define DEFAULT_MAXSVTSHEIGHT 100 |
maximum height to compute the SVTS score exactly before approximating
Definition at line 89 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 90 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 93 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 96 of file treemodel.c.
Typedef Documentation
◆ SCIP_RATIO
typedef struct SCIP_Ratio SCIP_RATIO |
Definition at line 141 of file treemodel.c.
Function Documentation
◆ SCIP_DECL_SORTINDCOMP()
|
static |
a comparison method for the next method. It simply compares two SCIP_Real
Definition at line 145 of file treemodel.c.
◆ findNonDominatedVars()
|
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 171 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 |
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 305 of file treemodel.c.
Referenced by findNonDominatedVars(), and selectCandidateUsingRatio().
◆ computeVarRatio()
|
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 331 of file treemodel.c.
References a, FALSE, SCIP_Var::history, SCIP_Ratio::invleft, LAGUERRE_THRESHOLD, SCIP_Treemodel::maxfpiter, r, SCIP_Bool, SCIP_Real, SCIPhistoryGetLastBalance(), SCIPhistoryGetLastRatio(), SCIPhistoryIsRatioValid(), SCIPhistorySetRatioHistory(), SCIPisEQ(), SCIPisGE(), SCIPisSumEQ(), SCIPisZero(), selectCandidateUsingRatio(), TRUE, SCIP_Ratio::upratio, and SCIP_Ratio::valid.
Referenced by computeSampleTreesize(), computeSVTS(), and selectCandidateUsingRatio().
◆ selectCandidateUsingRatio()
|
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 455 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 |
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 498 of file treemodel.c.
References computeVarRatio(), SCIP_Ratio::invleft, SCIP_Treemodel::maxsvtsheight, 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 |
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 584 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()
computes a^b for integer b
- Parameters
-
a the base b the integer exponent
Definition at line 675 of file treemodel.c.
References a, computeSampleTreesize(), and SCIP_Real.
Referenced by computeSampleTreesize(), and selectCandidateUsingSVTS().
◆ computeSampleTreesize()
|
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 694 of file treemodel.c.
References computeVarRatio(), integerpow(), SCIP_Ratio::invleft, SCIP_Real, SCIP_REAL_MAX, selectCandidateUsingSampling(), SCIP_Ratio::upratio, and SCIP_Ratio::valid.
Referenced by integerpow(), and selectCandidateUsingSampling().
◆ selectCandidateUsingSampling()
|
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 743 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 834 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 892 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 908 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 920 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().