Detailed Description
methods and files provided by the default branching rules of SCIP
A detailed description what a branching rule does and how to add a branching rule to SCIP can be found here.
Modules | |
Inclusion methods | |
methods to include specific branching rules into SCIP | |
Functions | |
void | SCIPvarCalcDistributionParameters (SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance) |
SCIP_Real | SCIPcalcCumulativeDistribution (SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value) |
SCIP_Real | SCIProwCalcProbability (SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup) |
SCIP_RETCODE | SCIPupdateDistributionScore (SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam) |
SCIP_RETCODE | SCIPselectVarStrongBranching (SCIP *scip, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Bool *skipdown, SCIP_Bool *skipup, int nlpcands, int npriolpcands, int ncomplete, int *start, int maxproprounds, SCIP_Bool probingbounds, SCIP_Bool forcestrongbranch, int *bestcand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result) |
SCIP_RETCODE | SCIPselectBranchVarPscost (SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsscore, int nbranchcands, SCIP_VAR **var, SCIP_Real *brpoint) |
SCIP_RETCODE | SCIPexecRelpscostBranching (SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result) |
Files | |
file | branch_allfullstrong.h |
all variables full strong LP branching rule | |
file | branch_cloud.h |
cloud branching rule | |
file | branch_distribution.c |
probability based branching rule based on an article by J. Pryor and J.W. Chinneck | |
file | branch_distribution.h |
probability based branching rule based on an article by J. Pryor and J.W. Chinneck | |
file | branch_fullstrong.h |
full strong LP branching rule | |
file | branch_inference.h |
inference history branching rule | |
file | branch_leastinf.h |
least infeasible LP branching rule | |
file | branch_lookahead.c |
lookahead LP branching rule | |
file | branch_lookahead.h |
lookahead LP branching rule | |
file | branch_mostinf.h |
most infeasible LP branching rule | |
file | branch_multaggr.h |
fullstrong branching on fractional and multi-aggregated variables | |
file | branch_nodereopt.h |
nodereopt branching rule | |
file | branch_pscost.h |
pseudo costs branching rule | |
file | branch_random.h |
random variable branching rule | |
file | branch_relpscost.h |
reliable pseudo costs branching rule | |
file | branch_vanillafullstrong.h |
vanilla full strong LP branching rule | |
file | branch_multinode.h |
multinode branching rule | |
file | branch_ryanfoster.c |
Ryan/Foster branching rule. | |
Function Documentation
◆ SCIPvarCalcDistributionParameters()
void SCIPvarCalcDistributionParameters | ( | SCIP * | scip, |
SCIP_Real | varlb, | ||
SCIP_Real | varub, | ||
SCIP_VARTYPE | vartype, | ||
SCIP_Real * | mean, | ||
SCIP_Real * | variance | ||
) |
calculate the variable's distribution parameters (mean and variance) for the bounds specified in the arguments. special treatment of infinite bounds necessary
- Parameters
-
scip SCIP data structure varlb variable lower bound varub variable upper bound vartype type of the variable mean pointer to store mean value variance pointer to store the variance of the variable uniform distribution
Definition at line 260 of file branch_distribution.c.
References NULL, SCIP_VARTYPE_CONTINUOUS, SCIPisInfinity(), SCIPisNegative(), and SQUARED.
Referenced by calcBranchScore(), rowCalculateGauss(), and varProcessBoundChanges().
◆ SCIPcalcCumulativeDistribution()
SCIP_Real SCIPcalcCumulativeDistribution | ( | SCIP * | scip, |
SCIP_Real | mean, | ||
SCIP_Real | variance, | ||
SCIP_Real | value | ||
) |
calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed random variable x takes a value between -infinity and parameter value
.
The distribution is given by the respective mean and deviation. This implementation uses the error function erf().
calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed random variable x takes a value between -infinity and parameter value
.
The distribution is given by the respective mean and deviation. This implementation uses the error function SCIPerf().
- Parameters
-
scip current SCIP mean the mean value of the distribution variance the square of the deviation of the distribution value the upper limit of the calculated distribution integral
Definition at line 305 of file branch_distribution.c.
References SCIP_Real, SCIPdebugMsg, SCIPerf(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisNegative(), and SQRTOFTWO.
Referenced by SCIProwCalcProbability().
◆ SCIProwCalcProbability()
SCIP_Real SCIProwCalcProbability | ( | SCIP * | scip, |
SCIP_ROW * | row, | ||
SCIP_Real | mu, | ||
SCIP_Real | sigma2, | ||
int | rowinfinitiesdown, | ||
int | rowinfinitiesup | ||
) |
calculates the probability of satisfying an LP-row under the assumption of uniformly distributed variable values.
For inequalities, we use the cumulative distribution function of the standard normal distribution PHI(rhs - mu/sqrt(sigma2)) to calculate the probability for a right hand side row with mean activity mu and variance sigma2 to be satisfied. Similarly, 1 - PHI(lhs - mu/sqrt(sigma2)) is the probability to satisfy a left hand side row. For equations (lhs==rhs), we use the centeredness measure p = min(PHI(lhs'), 1-PHI(lhs'))/max(PHI(lhs'), 1 - PHI(lhs')), where lhs' = lhs - mu / sqrt(sigma2).
- Parameters
-
scip current scip row the row mu the mean value of the row distribution sigma2 the variance of the row distribution rowinfinitiesdown the number of variables with infinite bounds to DECREASE activity rowinfinitiesup the number of variables with infinite bounds to INCREASE activity
Definition at line 369 of file branch_distribution.c.
References MAX, NULL, SCIP_Real, SCIPcalcCumulativeDistribution(), SCIPdebug, SCIPdebugMsg, SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPprintRow(), SCIProwGetLhs(), SCIProwGetName(), and SCIProwGetRhs().
Referenced by calcBranchScore().
◆ SCIPupdateDistributionScore()
SCIP_RETCODE SCIPupdateDistributionScore | ( | SCIP * | scip, |
SCIP_Real | currentprob, | ||
SCIP_Real | newprobup, | ||
SCIP_Real | newprobdown, | ||
SCIP_Real * | upscore, | ||
SCIP_Real * | downscore, | ||
char | scoreparam | ||
) |
update the up- and downscore of a single variable after calculating the impact of branching on a particular row, depending on the chosen score parameter
- Parameters
-
scip current SCIP pointer currentprob the current probability newprobup the new probability if branched upwards newprobdown the new probability if branched downwards upscore pointer to store the new score for branching up downscore pointer to store the new score for branching down scoreparam parameter to determine the way the score is calculated
Definition at line 549 of file branch_distribution.c.
References NULL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPerrorMessage, SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGT(), and SCIPisLT().
Referenced by calcBranchScore().
◆ SCIPselectVarStrongBranching()
SCIP_RETCODE SCIPselectVarStrongBranching | ( | SCIP * | scip, |
SCIP_VAR ** | lpcands, | ||
SCIP_Real * | lpcandssol, | ||
SCIP_Real * | lpcandsfrac, | ||
SCIP_Bool * | skipdown, | ||
SCIP_Bool * | skipup, | ||
int | nlpcands, | ||
int | npriolpcands, | ||
int | ncomplete, | ||
int * | start, | ||
int | maxproprounds, | ||
SCIP_Bool | probingbounds, | ||
SCIP_Bool | forcestrongbranch, | ||
int * | bestcand, | ||
SCIP_Real * | bestdown, | ||
SCIP_Real * | bestup, | ||
SCIP_Real * | bestscore, | ||
SCIP_Bool * | bestdownvalid, | ||
SCIP_Bool * | bestupvalid, | ||
SCIP_Real * | provedbound, | ||
SCIP_RESULT * | result | ||
) |
Selects a variable from a set of candidates by strong branching
- Returns
- SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See SCIP_RETCODE for a complete list of error codes.
- Note
- The variables in the lpcands array must have a fractional value in the current LP solution
- Parameters
-
scip original SCIP data structure lpcands branching candidates lpcandssol solution values of the branching candidates lpcandsfrac fractional values of the branching candidates skipdown should down branchings be skipped? skipup should up branchings be skipped? nlpcands number of branching candidates npriolpcands number of priority branching candidates ncomplete number of branching candidates without skip start starting index in lpcands maxproprounds maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings) probingbounds should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)? forcestrongbranch should strong branching be applied even if there is just a single candidate? bestcand best candidate for branching bestdown objective value of the down branch for bestcand bestup objective value of the up branch for bestcand bestscore score for bestcand bestdownvalid is bestdown a valid dual bound for the down branch? bestupvalid is bestup a valid dual bound for the up branch? provedbound proved dual bound for current subtree result result pointer
Definition at line 173 of file branch_fullstrong.c.
References BRANCHRULE_NAME, FALSE, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_BRANCHEXECLP(), SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPdebug, SCIPdebugMsg, SCIPendStrongbranch(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfindBranchrule(), SCIPfreeBufferArray, SCIPgetBranchScore(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPgetNVars(), SCIPgetVars(), SCIPgetVarStrongbranchFrac(), SCIPgetVarStrongbranchLast(), SCIPgetVarStrongbranchLPAge(), SCIPgetVarStrongbranchNode(), SCIPgetVarStrongbranchWithPropagation(), SCIPinfinity(), SCIPisExactSolve(), SCIPisFeasZero(), SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPisStopped(), SCIPprintDisplayLine(), SCIPstartStrongbranch(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPverbMessage(), and TRUE.
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ SCIPselectBranchVarPscost()
SCIP_RETCODE SCIPselectBranchVarPscost | ( | SCIP * | scip, |
SCIP_VAR ** | branchcands, | ||
SCIP_Real * | branchcandssol, | ||
SCIP_Real * | branchcandsscore, | ||
int | nbranchcands, | ||
SCIP_VAR ** | var, | ||
SCIP_Real * | brpoint | ||
) |
selects a branching variable, due to pseudo cost, from the given candidate array and returns this variable together with a branching point
- Parameters
-
scip SCIP data structure branchcands branching candidates branchcandssol solution value for the branching candidates branchcandsscore array of candidate scores nbranchcands number of branching candidates var pointer to store the variable to branch on, or NULL if none brpoint pointer to store the branching point for the branching variable, will be fractional for a discrete variable
Definition at line 814 of file branch_pscost.c.
References BRANCHRULE_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPfindBranchrule(), and selectBranchVar().
◆ SCIPexecRelpscostBranching()
SCIP_RETCODE SCIPexecRelpscostBranching | ( | SCIP * | scip, |
SCIP_VAR ** | branchcands, | ||
SCIP_Real * | branchcandssol, | ||
SCIP_Real * | branchcandsfrac, | ||
int | nbranchcands, | ||
SCIP_Bool | executebranching, | ||
SCIP_RESULT * | result | ||
) |
execution reliability pseudo cost branching with the given branching candidates
- Parameters
-
scip SCIP data structure branchcands branching candidates branchcandssol solution value for the branching candidates branchcandsfrac fractional part of the branching candidates nbranchcands number of branching candidates executebranching perform a branching step after probing result pointer to the result of the execution
Definition at line 2224 of file branch_relpscost.c.
References BRANCHRULE_NAME, execRelpscost(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPfindBranchrule().
Referenced by SCIP_DECL_BRANCHEXECLP().