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:
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 |
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) |
#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().
#define DEFAULT_ENABLE FALSE |
should candidate branching variables be scored using the Treemodel rule?
Definition at line 72 of file treemodel.c.
Referenced by SCIPtreemodelInit().
#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.
Referenced by SCIPtreemodelInit().
#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 75 of file treemodel.c.
Referenced by SCIPtreemodelInit().
#define DEFAULT_HEIGHT 10 |
estimated tree height at which we switch from using the low rule to the high rule
Definition at line 77 of file treemodel.c.
Referenced by SCIPtreemodelInit().
#define DEFAULT_FILTERHIGH 'a' |
should dominated candidates be filtered before using the high scoring function? ('a'uto, 't'rue, 'f'alse)
Definition at line 79 of file treemodel.c.
Referenced by SCIPtreemodelInit().
#define DEFAULT_FILTERLOW 'a' |
should dominated candidates be filtered before using the low scoring function? ('a'uto, 't'rue, 'f'alse)
Definition at line 81 of file treemodel.c.
Referenced by SCIPtreemodelInit().
#define DEFAULT_MAXFPITER 24 |
maximum number of fixed-point iterations when computing the ratio
Definition at line 83 of file treemodel.c.
Referenced by SCIPtreemodelInit().
#define DEFAULT_MAXSVTSHEIGHT 100 |
maximum height to compute the SVTS score exactly before approximating
Definition at line 84 of file treemodel.c.
Referenced by SCIPtreemodelInit().
#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 85 of file treemodel.c.
Referenced by SCIPtreemodelInit().
#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 87 of file treemodel.c.
Referenced by SCIPtreemodelInit().
#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 89 of file treemodel.c.
Referenced by SCIPtreemodelInit().
typedef struct SCIP_Ratio SCIP_RATIO |
Definition at line 133 of file treemodel.c.
|
static |
a comparison method for the next method. It simply compares two SCIP_Real
Definition at line 137 of file treemodel.c.
|
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.
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 163 of file treemodel.c.
References a, assert(), b, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGT(), SCIPisLT(), SCIPsortDownInd(), and TRUE.
Referenced by SCIPtreemodelSelectCandidate().
|
static |
returns true iff the variable with given gains has a ratio better (i.e smaller) than the given one
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 297 of file treemodel.c.
References assert(), SCIP_Ratio::invleft, NULL, result, SCIP_Bool, SCIP_Real, SCIPisLE(), SCIP_Ratio::upratio, and SCIP_Ratio::valid.
Referenced by selectCandidateUsingRatio().
|
static |
computes the variable ratio corresponding to the left and right gains
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 323 of file treemodel.c.
References a, assert(), FALSE, SCIP_Ratio::invleft, LAGUERRE_THRESHOLD, SCIP_Treemodel::maxfpiter, r, SCIP_Real, SCIPhistoryGetLastBalance(), SCIPhistoryGetLastRatio(), SCIPhistoryIsRatioValid(), SCIPhistorySetRatioHistory(), SCIPisEQ(), SCIPisGE(), SCIPisSumEQ(), SCIPisZero(), TRUE, SCIP_Ratio::upratio, SCIP_Ratio::valid, and var.
Referenced by computeSampleTreesize(), computeSVTS(), and selectCandidateUsingRatio().
|
static |
use the Ratio scoring function to select a branching candidate
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 447 of file treemodel.c.
References bestcand, c, computeVarRatio(), hasBetterRatio(), SCIP_Bool, SCIP_OKAY, SCIP_Real, and SCIP_Ratio::valid.
Referenced by SCIPtreemodelSelectCandidate(), selectCandidateUsingSampling(), and selectCandidateUsingSVTS().
|
static |
Returns the predicted treesize for the gap and given up and down gains
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 490 of file treemodel.c.
References assert(), computeVarRatio(), SCIP_Ratio::invleft, SCIP_Treemodel::maxsvtsheight, SCIP_Real, SCIP_REAL_MAX, SCIPceil(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIP_Ratio::upratio, SCIP_Ratio::valid, and var.
Referenced by selectCandidateUsingSVTS().
|
static |
use the SVTS scoring function to select a branching candidate
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 576 of file treemodel.c.
References bestcand, c, computeSVTS(), SCIP_Treemodel::fallbackinf, SCIP_Treemodel::fallbacknoprim, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), and selectCandidateUsingRatio().
Referenced by SCIPtreemodelSelectCandidate().
computes a^b for integer b
a | the base |
b | the integer exponent |
Definition at line 667 of file treemodel.c.
References a, b, and SCIP_Real.
Referenced by computeSampleTreesize().
|
static |
returns the sampled tree size for the given lp gains and dual gap
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 686 of file treemodel.c.
References computeVarRatio(), integerpow(), SCIP_Ratio::invleft, SCIP_Real, SCIP_REAL_MAX, SCIP_Ratio::upratio, SCIP_Ratio::valid, and var.
Referenced by selectCandidateUsingSampling().
|
static |
use the Tree Sampling scoring function to select a branching candidate
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 735 of file treemodel.c.
References bestcand, c, computeSampleTreesize(), SCIP_Treemodel::fallbackinf, SCIP_Treemodel::fallbacknoprim, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), and selectCandidateUsingRatio().
Referenced by SCIPtreemodelSelectCandidate().
SCIP_RETCODE SCIPtreemodelInit | ( | SCIP * | scip, |
SCIP_TREEMODEL ** | treemodel ) |
initialises the Treemodel parameter data structure
scip | SCIP data structure |
treemodel | Treemodel parameter data structure |
Definition at line 826 of file treemodel.c.
References assert(), DEFAULT_ENABLE, DEFAULT_FALLBACKINF, DEFAULT_FALLBACKNOPRIM, DEFAULT_FILTERHIGH, DEFAULT_FILTERLOW, DEFAULT_HEIGHT, DEFAULT_HIGHRULE, DEFAULT_LOWRULE, DEFAULT_MAXFPITER, DEFAULT_MAXSVTSHEIGHT, DEFAULT_SMALLPSCOST, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, and TRUE.
Referenced by SCIPincludeBranchruleRelpscost().
SCIP_RETCODE SCIPtreemodelFree | ( | SCIP * | scip, |
SCIP_TREEMODEL ** | treemodel ) |
frees the Treemodel parameter data structure
scip | SCIP data structure |
treemodel | Treemodel parameter data structure |
Definition at line 884 of file treemodel.c.
References assert(), NULL, SCIP_OKAY, and SCIPfreeBlockMemory.
Referenced by SCIP_DECL_BRANCHFREE().
SCIP_Bool SCIPtreemodelIsEnabled | ( | SCIP * | scip, |
SCIP_TREEMODEL * | treemodel ) |
returns TRUE if the Treemodel branching rules are enabled
scip | SCIP data structure |
treemodel | Treemodel parameter data structure |
Definition at line 900 of file treemodel.c.
References assert(), SCIP_Treemodel::enabled, NULL, and SCIP_Bool.
Referenced by execRelpscost().
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
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 912 of file treemodel.c.
References assert(), bestcand, SCIP_Treemodel::enabled, SCIP_Treemodel::filterhigh, SCIP_Treemodel::filterlow, findNonDominatedVars(), 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().