branch_distribution.h File Reference

Detailed Description

probability based branching rule based on an article by J. Pryor and J.W. Chinneck

Author

Gregor Hendel

The distribution branching rule selects a variable based on its impact on row activity distributions. More formally, let \( a(x) = a_1 x_1 + \dots + a_n x_n \leq b \) be a row of the LP. Let further \( l_i, u_i \in R\) denote the (finite) lower and upper bound, respectively, of the \( i \)-th variable \(x_i\). Viewing every variable \(x_i \) as (continuously) uniformly distributed within its bounds, we can approximately understand the row activity \(a(x)\) as a gaussian random variate with mean value \( \mu = E[a(x)] = \sum_i a_i\frac{l_i + u_i}{2}\) and variance \( \sigma^2 = \sum_i a_i^2 \sigma_i^2 \), with \( \sigma_i^2 = \frac{(u_i - l_i)^2}{12}\) for continuous and \( \sigma_i^2 = \frac{(u_i - l_i + 1)^2 - 1}{12}\) 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: \( P(a(x) \leq b) = \Phi(\frac{b - \mu}{\sigma})\).

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 scoreparam. For both branching directions, an individual score is calculated. Available options for scoring methods are:

• d: select a branching variable with largest difference in satisfaction probability after branching
• l: lowest cumulative probability amongst all variables on all rows (after branching).
• h: highest cumulative probability amongst all variables on all rows (after branching).
• v: highest number of votes for lowering row probability for all rows a variable appears in.
• w: highest number of votes for increasing row probability for all rows a variable appears in.

If the parameter usescipscore is set to TRUE, a single branching score is calculated from the respective up and down scores as defined by the SCIP branching score function (see advanced branching parameter scorefunc), otherwise, the variable with the single highest score is selected, and the maximizing direction is assigned higher branching priority.

The original idea of probability based branching schemes appeared in:

J. Pryor and J.W. Chinneck:
Faster Integer-Feasibility in Mixed-Integer Linear Programs by Branching to Force Change
Computers and Operations Research, vol. 38, 2011, p. 1143–1152
(http://www.sce.carleton.ca/faculty/chinneck/docs/PryorChinneck.pdf)

Definition in file branch_distribution.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeBranchruleDistribution (SCIP *scip)
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)