69#define LAGUERRE_THRESHOLD 100
72#define DEFAULT_ENABLE FALSE
73#define DEFAULT_HIGHRULE 'r'
75#define DEFAULT_LOWRULE 'r'
77#define DEFAULT_HEIGHT 10
79#define DEFAULT_FILTERHIGH 'a'
81#define DEFAULT_FILTERLOW 'a'
83#define DEFAULT_MAXFPITER 24
84#define DEFAULT_MAXSVTSHEIGHT 100
85#define DEFAULT_FALLBACKINF 'r'
87#define DEFAULT_FALLBACKNOPRIM 'r'
89#define DEFAULT_SMALLPSCOST 0.1
143 assert(ind1 >= 0 && ind2 >= 0);
145 diffval = value[ind1] - value[ind2];
148 else if( diffval > 0.0)
195 for( origindex=0; origindex<size; ++origindex )
196 permb[origindex] = origindex;
205 bestcurrenta =
a[permb[0]];
208 currentb =
b[permb[0]];
210 bestcurrents[0] = permb[0];
214 for( indexinpermb = 1; indexinpermb < size; ++indexinpermb )
216 origindex = permb[indexinpermb];
217 assert(
b[origindex] <= currentb);
223 if( bestcurrenta > besta )
225 for( iterbestcurrent=0; iterbestcurrent < nbestcurrent; ++iterbestcurrent )
226 dominated[bestcurrents[iterbestcurrent]] =
FALSE;
228 besta = bestcurrenta;
232 for( iterbestcurrent = 0; iterbestcurrent < nbestcurrent; ++iterbestcurrent )
234 dominated[bestcurrents[iterbestcurrent]] =
TRUE;
238 bestcurrenta =
a[origindex];
239 currentb =
b[origindex];
240 bestcurrents[0] = origindex;
249 for( iterbestcurrent = 0; iterbestcurrent < nbestcurrent; ++iterbestcurrent )
251 dominated[bestcurrents[iterbestcurrent]] =
TRUE;
255 bestcurrenta =
a[origindex];
256 bestcurrents[0] = origindex;
264 bestcurrents[nbestcurrent] = origindex;
269 dominated[origindex] =
TRUE;
276 if( bestcurrenta > besta )
278 for( iterbestcurrent = 0; iterbestcurrent < nbestcurrent; ++iterbestcurrent )
279 dominated[bestcurrents[iterbestcurrent]] =
FALSE;
283 for( iterbestcurrent = 0; iterbestcurrent < nbestcurrent; ++iterbestcurrent )
285 dominated[bestcurrents[iterbestcurrent]] =
TRUE;
312 if( leftgain > 0.0 && rightgain > 0.0 )
347 r = rightgain / leftgain;
354 branchratio->
invleft = 1.0 / leftgain;
363 branchratio->
invleft = 1.0 / leftgain;
373 newratio = pow(2.0, 1.0/
r);
388 for( iters = 0; ((iters <= 5 && !
SCIPisEQ(
scip, ratio, newratio)) ||
390 && iters < treemodel->
maxfpiter && newratio > 1.0; iters++ )
392 double G, H,
a, p, p1, p2, phi_r;
395 phi_r = pow(ratio,
r);
396 p = phi_r - phi_r / ratio - 1.0;
399 p1 = (
r * phi_r - (
r - 1.0) * phi_r / ratio) / ratio;
400 p2 = (
r * (
r - 1.0) * phi_r - (
r - 1.0) * (
r - 2.0) * phi_r / ratio) / ratio / ratio;
402 H = G * G - (p2 / p);
403 a =
r / (G + (G >= 0 ? 1.0 : -1.0) * sqrt((
r - 1.0) * (
r * H - G * G)));
404 newratio = ratio -
a;
413 for( iters = 0; ((iters <= 10 && !
SCIPisEQ(
scip, ratio, newratio)) ||
415 && iters < treemodel->
maxfpiter && newratio > 1; iters++ )
418 newratio = pow(1.0-1.0/ratio, -1.0/
r);
427 if( iters < treemodel->maxfpiter && newratio > 1.0 )
430 branchratio->
upratio = (ratio + newratio) / 2.0;
431 branchratio->
invleft = 1.0 / leftgain;
467 computeVarRatio(
scip, treemodel, branchcands[referencevar], mingains[referencevar], maxgains[referencevar], &bestbranchratio);
469 for(
c = 0;
c < nbranchcands; ++
c )
471 if( (!filterdominated || !dominated[
c]) &&
c != referencevar )
476 if( branchratio.
valid )
479 bestbranchratio = branchratio;
513 scaledgain = maxgain / mingain;
514 scaledgap = absgap / mingain;
516 mindepth = (int)
SCIPceil(
scip, scaledgap / scaledgain);
522 gaptoreach = scaledgap * (treemodel->
maxsvtsheight - 1) / mindepth;
525 assert(gaptoreach > scaledgain);
529 gaptoreach = scaledgap;
532 mindepth = (int) ceil(gaptoreach / scaledgain);
533 assert(mindepth <= treemodel->maxsvtsheight);
537 for( nr = 1; nr <= mindepth; ++nr )
540 for( ir = 1; ir <= nr; ++ir )
542 binomcoeff *= (nr + ceil((gaptoreach - (nr - 1) * scaledgain)) - ir) / ir;
544 treesize += binomcoeff;
547 treesize = 2.0 * treesize - 1.0;
561 if( branchratio.
valid )
562 prediction = treesize * pow(branchratio.
upratio, (scaledgap - gaptoreach) * branchratio.
invleft);
567 prediction = treesize;
611 referencetreesize =
computeSVTS(
scip, treemodel, branchcands[referencevar], localabsgap, mingains[referencevar],
612 maxgains[referencevar]);
616 treesizes[referencevar] = referencetreesize;
618 for(
c = 0;
c < nbranchcands; ++
c )
620 if( !filterdominated || !dominated[
c] )
622 if(
c != referencevar )
623 treesizes[
c] =
computeSVTS(
scip, treemodel, branchcands[
c], localabsgap, mingains[
c], maxgains[
c]);
625 treesizes[
c] = referencetreesize;
627 avgtreesize += treesizes[
c];
632 avgtreesize = avgtreesize / (nbranchcands - ndominated);
634 for(
c = 0;
c < nbranchcands; ++
c )
636 score = (1.0 - 1.0 / (1.0 + avgtreesize / treesizes[
c])) + 0.01 * tiebreakerscore[
c];
637 if(score > bestscore)
703 if( branchratio.
valid )
707 int kl = (int)ceil(absgap / leftgain);
708 int kr = (int)ceil(absgap / rightgain);
709 int k = (int)ceil(absgap / (leftgain + rightgain));
715 leftsize = (
integerpow(phi_l, kl + 1) - 1.0) / (phi_l - 1.0);
716 rightsize = (
integerpow(phi_r, kr + 1) - 1.0) / (phi_r - 1.0);
718 if( k * (leftgain + rightgain) < absgap + rightgain )
719 midsize = (1.0 + phi_l) * (phi_klr * phi_lr - 1.0) / (phi_lr - 1.0) - phi_klr * phi_l;
721 midsize = (1.0 + phi_l) * (phi_klr - 1.0) / (phi_lr - 1.0);
723 prediction = (leftsize + rightsize + midsize) / 3.0;
770 referencetreesize =
computeSampleTreesize(
scip, treemodel, branchcands[referencevar], localabsgap, mingains[referencevar],
771 maxgains[referencevar]);
776 treesizes[referencevar] = referencetreesize;
778 for(
c = 0;
c < nbranchcands; ++
c )
780 if( !filterdominated || !dominated[
c] )
782 if(
c != referencevar )
785 treesizes[
c] = referencetreesize;
787 avgtreesize += treesizes[
c];
792 avgtreesize = avgtreesize / (nbranchcands - ndominated);
794 for(
c = 0;
c < nbranchcands; ++
c )
796 score = (1.0 - 1.0 / (1.0 + avgtreesize / treesizes[
c])) + 0.01 * tiebreakerscore[
c];
797 if( score > bestscore )
836 "should candidate branching variables be scored using the Treemodel branching rules?",
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)",
848 "estimated tree height at which we switch from using the low rule to the high rule",
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)",
860 "maximum number of fixed-point iterations when computing the ratio",
864 "maximum height to compute the SVTS score exactly before approximating",
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",
926 char scoringfunction;
942 bestcandheight = (int)(localabsgap/mingains[*
bestcand]);
944 bestcandheight = INT_MAX;
947 if( bestcandheight < treemodel->height )
949 scoringfunction = treemodel->
lowrule;
954 scoringfunction = treemodel->
highrule;
959 if( scoringfunction !=
'd' )
967 autofilter = (filtersetting ==
'a' && (scoringfunction ==
's' || scoringfunction ==
't'));
968 filterdominated = (autofilter || filtersetting ==
't');
971 if( filterdominated )
983 switch( scoringfunction )
987 localabsgap, filterdominated, dominated, nbranchcands, ndominated,
bestcand) );
991 dominated, nbranchcands,
bestcand) );
995 localabsgap, filterdominated, dominated, nbranchcands, ndominated,
bestcand) );
1002 if( filterdominated )
SCIP_Real SCIPgetNodeLowerbound(SCIP *scip, SCIP_NODE *node)
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)
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)
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)
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)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
void SCIPsortDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
assert(minobj< SCIPgetCutoffbound(scip))
void SCIPhistorySetRatioHistory(SCIP_HISTORY *history, SCIP_Bool valid, SCIP_Real ratio, SCIP_Real balance)
SCIP_Real SCIPhistoryGetLastRatio(SCIP_HISTORY *history)
SCIP_Bool SCIPhistoryIsRatioValid(SCIP_HISTORY *history)
SCIP_Real SCIPhistoryGetLastBalance(SCIP_HISTORY *history)
internal methods for branching and inference history
static SCIP_Real integerpow(SCIP_Real a, int b)
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)
struct SCIP_Ratio SCIP_RATIO
#define DEFAULT_FALLBACKNOPRIM
static SCIP_RETCODE findNonDominatedVars(SCIP *scip, SCIP_Real *a, SCIP_Real *b, int size, int *ndominated, SCIP_Bool *dominated)
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)
SCIP_RETCODE SCIPtreemodelFree(SCIP *scip, SCIP_TREEMODEL **treemodel)
#define DEFAULT_FILTERLOW
static SCIP_Real computeSampleTreesize(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real leftgain, SCIP_Real rightgain)
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_Bool hasBetterRatio(SCIP *scip, SCIP_RATIO *branchratio, SCIP_Real leftgain, SCIP_Real rightgain)
#define DEFAULT_SMALLPSCOST
#define DEFAULT_MAXFPITER
static SCIP_Real computeSVTS(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real mingain, SCIP_Real maxgain)
SCIP_Bool SCIPtreemodelIsEnabled(SCIP *scip, SCIP_TREEMODEL *treemodel)
#define DEFAULT_FILTERHIGH
static void computeVarRatio(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real leftgain, SCIP_Real rightgain, SCIP_RATIO *branchratio)
#define LAGUERRE_THRESHOLD
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)
#define DEFAULT_MAXSVTSHEIGHT
#define DEFAULT_FALLBACKINF
Branching rules based on the Single-Variable-Branching (SVB) model.
struct SCIP_Treemodel SCIP_TREEMODEL
#define SCIP_DECL_SORTINDCOMP(x)
enum SCIP_Retcode SCIP_RETCODE
internal methods for problem variables