# 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

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 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