treemodel.c
Go to the documentation of this file.
60/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
69#define LAGUERRE_THRESHOLD 100 /**< Maximum value of r/l at which Laguerre is the prefered FP method */
72#define DEFAULT_ENABLE FALSE /**< should candidate branching variables be scored using the Treemodel rule? */
73#define DEFAULT_HIGHRULE 'r' /**< scoring function to use at nodes predicted to be high in the tree.
77#define DEFAULT_HEIGHT 10 /**< estimated tree height at which we switch from using the low rule to
79#define DEFAULT_FILTERHIGH 'a' /**< should dominated candidates be filtered before using the high scoring
81#define DEFAULT_FILTERLOW 'a' /**< should dominated candidates be filtered before using the low scoring
83#define DEFAULT_MAXFPITER 24 /**< maximum number of fixed-point iterations when computing the ratio */
84#define DEFAULT_MAXSVTSHEIGHT 100 /**< maximum height to compute the SVTS score exactly before approximating */
85#define DEFAULT_FALLBACKINF 'r' /**< which method should be used as a fallback if the tree size estimates are
87#define DEFAULT_FALLBACKNOPRIM 'r' /**< which method should be used as a fallback if there is no primal bound
89#define DEFAULT_SMALLPSCOST 0.1 /**< threshold at which pseudocosts are considered small, making hybrid scores
120 * A variable's ratio is defined based upon its left and right LP gains, as the unique root > 1 of
220 /* If the above is true, then we went through all the previous elements that had value currentb */
221 /* Thus the best element for value currentb is non-dominated if its value bestcurrenta is better
295/** returns true iff the variable with given gains has a ratio better (i.e smaller) than the given one */
314 result = pow(branchratio->upratio, rightgain * branchratio->invleft) - pow(branchratio->upratio, (rightgain - leftgain) * branchratio->invleft) - 1; /*lint !e644*/
359 if( SCIPhistoryIsRatioValid(var->history) && SCIPisEQ(scip, SCIPhistoryGetLastBalance(var->history), r) )
378 /* Depending on the value of rightgain/leftgain, we have two different methods to compute the ratio
379 * If this value is bigger than 100, we use a fixed-point method. Otherwise, we use Laguerre's method
386 /* We relax the epsilon after 5 iterations since we may not have enough precision to achieve any better
411 /* We relax the epsilon after 10 iterations since we may not have enough precision to achieve any better
423 * Note that the fixed point method is not guaranteed to converge due to numerical precision issues.
467 computeVarRatio(scip, treemodel, branchcands[referencevar], mingains[referencevar], maxgains[referencevar], &bestbranchratio);
473 if( !bestbranchratio.valid || hasBetterRatio(scip, &bestbranchratio, mingains[c], maxgains[c]) ) /*lint !e644*/
494 SCIP_Real absgap, /**< the absolute gap to close (typically the local gap at the current node) */
562 prediction = treesize * pow(branchratio.upratio, (scaledgap - gaptoreach) * branchratio.invleft); /*lint !e644*/
601 /* We will first measure the treesize for scip's default variable. If it is infinite then we don't compute
602 * the treesize for other variables (even though it might be finite) and go directly to the fallback strategy */
611 referencetreesize = computeSVTS(scip, treemodel, branchcands[referencevar], localabsgap, mingains[referencevar],
623 treesizes[c] = computeSVTS(scip, treemodel, branchcands[c], localabsgap, mingains[c], maxgains[c]);
651 SCIP_CALL( selectCandidateUsingRatio(scip, treemodel, branchcands, mingains, maxgains, filterdominated, dominated,
658 SCIP_CALL( selectCandidateUsingRatio(scip, treemodel, branchcands, mingains, maxgains, filterdominated, dominated,
760 /* We will first measure the treesize for scip's default variable. If it is infinite then we don't compute
761 * the treesize for other variables (even though it might be finite) and go directly to the fallback strategy */
770 referencetreesize = computeSampleTreesize(scip, treemodel, branchcands[referencevar], localabsgap, mingains[referencevar],
783 treesizes[c] = computeSampleTreesize(scip, treemodel, branchcands[c], localabsgap, mingains[c], maxgains[c]);
811 SCIP_CALL( selectCandidateUsingRatio(scip, treemodel, branchcands, mingains, maxgains, filterdominated, dominated,
818 SCIP_CALL( selectCandidateUsingRatio(scip, treemodel, branchcands, mingains, maxgains, filterdominated, dominated,
840 "scoring function to use at nodes predicted to be high in the tree ('d'efault, 's'vts, 'r'atio, 't'ree sample)",
844 "scoring function to use at nodes predicted to be low in the tree ('d'efault, 's'vts, 'r'atio, 't'ree sample)",
852 "should dominated candidates be filtered before using the high scoring function? ('a'uto, 't'rue, 'f'alse)",
856 "should dominated candidates be filtered before using the low scoring function? ('a'uto, 't'rue, 'f'alse)",
868 "which method should be used as a fallback if the tree size estimates are infinite? ('d'efault, 'r'atio)",
872 "which method should be used as a fallback if there is no primal bound available? ('d'efault, 'r'atio)",
876 "threshold at which pseudocosts are considered small, making hybrid scores more likely to be the deciding factor in branching",
974 SCIP_CALL( findNonDominatedVars(scip, mingains, maxgains, nbranchcands, &ndominated, dominated) );
986 SCIP_CALL( selectCandidateUsingSVTS(scip, treemodel, branchcands, mingains, maxgains, tiebreakerscore,
990 SCIP_CALL( selectCandidateUsingRatio(scip, treemodel, branchcands, mingains, maxgains, filterdominated,
994 SCIP_CALL( selectCandidateUsingSampling(scip, treemodel, branchcands, mingains, maxgains, tiebreakerscore,
SCIP_Real SCIPgetNodeLowerbound(SCIP *scip, SCIP_NODE *node)
Definition: scip_prob.c:3622
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:167
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:679
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
void SCIPsortDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
void SCIPhistorySetRatioHistory(SCIP_HISTORY *history, SCIP_Bool valid, SCIP_Real ratio, SCIP_Real balance)
Definition: history.c:793
SCIP_Real SCIPhistoryGetLastRatio(SCIP_HISTORY *history)
Definition: history.c:727
SCIP_Bool SCIPhistoryIsRatioValid(SCIP_HISTORY *history)
Definition: history.c:717
SCIP_Real SCIPhistoryGetLastBalance(SCIP_HISTORY *history)
Definition: history.c:738
internal methods for branching and inference history
Definition: objbenders.h:44
Definition: treemodel.c:127
Definition: treemodel.c:94
Definition: struct_var.h:208
Definition: struct_scip.h:70
SCIP_RETCODE SCIPtreemodelSelectCandidate(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Real *tiebreakerscore, int nbranchcands, int *bestcand)
Definition: treemodel.c:912
SCIP_RETCODE SCIPtreemodelInit(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition: treemodel.c:826
static SCIP_RETCODE findNonDominatedVars(SCIP *scip, SCIP_Real *a, SCIP_Real *b, int size, int *ndominated, SCIP_Bool *dominated)
Definition: treemodel.c:163
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)
Definition: treemodel.c:576
SCIP_RETCODE SCIPtreemodelFree(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition: treemodel.c:884
static SCIP_Real computeSampleTreesize(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real leftgain, SCIP_Real rightgain)
Definition: treemodel.c:686
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)
Definition: treemodel.c:447
static SCIP_Bool hasBetterRatio(SCIP *scip, SCIP_RATIO *branchratio, SCIP_Real leftgain, SCIP_Real rightgain)
Definition: treemodel.c:297
static SCIP_Real computeSVTS(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real mingain, SCIP_Real maxgain)
Definition: treemodel.c:490
SCIP_Bool SCIPtreemodelIsEnabled(SCIP *scip, SCIP_TREEMODEL *treemodel)
Definition: treemodel.c:900
static void computeVarRatio(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real leftgain, SCIP_Real rightgain, SCIP_RATIO *branchratio)
Definition: treemodel.c:323
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)
Definition: treemodel.c:735
Branching rules based on the Single-Variable-Branching (SVB) model.
internal methods for problem variables