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)

Function Documentation

SCIP_RETCODE SCIPincludeBranchruleDistribution ( SCIP * scip )

creates the distribution branching rule and includes it in SCIP

Parameters

scip	SCIP data structure

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

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().

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

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

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

SCIP

Detailed Description

Functions

Function Documentation