Scippy

SCIP

Solving Constraint Integer Programs

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)
 

Function Documentation

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
scipSCIP data structure
varlbvariable lower bound
varubvariable upper bound
vartypetype of the variable
meanpointer to store mean value
variancepointer to store the variance of the variable uniform distribution

Definition at line 235 of file branch_distribution.c.

References NULL, SCIP_VARTYPE_CONTINUOUS, SCIPisInfinity(), SCIPisNegative(), and SQUARED.

Referenced by calcBranchScore(), rowCalculateGauss(), and varProcessBoundChanges().

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
scipcurrent SCIP
meanthe mean value of the distribution
variancethe square of the deviation of the distribution
valuethe upper limit of the calculated distribution integral

Definition at line 280 of file branch_distribution.c.

References SCIP_Real, SCIPdebugMessage, SCIPerf(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisNegative(), sqrt(), and SQRTOFTWO.

Referenced by 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
scipcurrent scip
rowthe row
muthe mean value of the row distribution
sigma2the variance of the row distribution
rowinfinitiesdownthe number of variables with infinite bounds to DECREASE activity
rowinfinitiesupthe number of variables with infinite bounds to INCREASE activity

Definition at line 344 of file branch_distribution.c.

References MAX, MIN, NULL, SCIP_Real, SCIPcalcCumulativeDistribution(), SCIPdebug, SCIPdebugMessage, SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPprintRow(), SCIProwGetLhs(), SCIProwGetName(), and SCIProwGetRhs().

Referenced by calcBranchScore().

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
scipcurrent SCIP pointer
currentprobthe current probability
newprobupthe new probability if branched upwards
newprobdownthe new probability if branched downwards
upscorepointer to store the new score for branching up
downscorepointer to store the new score for branching down
scoreparamparameter to determine the way the score is calculated

Definition at line 524 of file branch_distribution.c.

References NULL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPerrorMessage, SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGT(), and SCIPisLT().

Referenced by calcBranchScore().