branch_distribution.h File Reference Detailed Descriptionprobability based branching rule based on an article by J. Pryor and J.W. Chinneck The distribution branching rule selects a variable based on its impact on row activity distributions. More formally, let be a row of the LP. Let further denote the (finite) lower and upper bound, respectively, of the -th variable . Viewing every variable as (continuously) uniformly distributed within its bounds, we can approximately understand the row activity as a gaussian random variate with mean value and variance , with for continuous and for discrete variables. With these two parameters, we can calculate the probability to satisfy the row in terms of the cumulative distribution of the standard normal distribution: . The impact of a variable on the probability to satisfy a constraint after branching can be estimated by altering the variable contribution to the sums described above. In order to keep the tree size small, variables are preferred which decrease the probability to satisfy a row because it is more likely to create infeasible subproblems. The selection of the branching variable is subject to the parameter
If the parameter The original idea of probability based branching schemes appeared in: J. Pryor and J.W. Chinneck: Definition in file branch_distribution.h. #include "scip/scip.h" Go to the source code of this file.
Function Documentation
creates the distribution branching rule and includes it in SCIP
calculate the variable's distribution parameters (mean and variance) for the bounds specified in the arguments. special treatment of infinite bounds necessary
calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed random variable x takes a value between -infinity and parameter The distribution is given by the respective mean and deviation. This implementation uses the error function erf().
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).
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
|