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.h.
#include "scip/scip.h"
Go to the source code of this file.
Functions | |
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) |
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().