branch_distribution.h
Go to the documentation of this file.
21 * The distribution branching rule selects a variable based on its impact on row activity distributions. More formally, 22 * let \f$ a(x) = a_1 x_1 + \dots + a_n x_n \leq b \f$ be a row of the LP. Let further \f$ l_i, u_i \in R\f$ denote the 24 * Viewing every variable \f$x_i \f$ as (continuously) uniformly distributed within its bounds, we can approximately 25 * understand the row activity \f$a(x)\f$ as a gaussian random variate with mean value \f$ \mu = E[a(x)] = \sum_i a_i\frac{l_i + u_i}{2}\f$ 26 * and variance \f$ \sigma^2 = \sum_i a_i^2 \sigma_i^2 \f$, with \f$ \sigma_i^2 = \frac{(u_i - l_i)^2}{12}\f$ for 28 * With these two parameters, we can calculate the probability to satisfy the row in terms of the cumulative distribution 31 * The impact of a variable on the probability to satisfy a constraint after branching can be estimated by altering 36 * The selection of the branching variable is subject to the parameter @p scoreparam. For both branching directions, 38 * - @b d: select a branching variable with largest difference in satisfaction probability after branching 41 * - @b v: highest number of votes for lowering row probability for all rows a variable appears in. 42 * - @b w: highest number of votes for increasing row probability for all rows a variable appears in. 44 * If the parameter @p usescipscore is set to @a TRUE, a single branching score is calculated from the respective 45 * up and down scores as defined by the SCIP branching score function (see advanced branching parameter @p scorefunc), 46 * otherwise, the variable with the single highest score is selected, and the maximizing direction is assigned 57 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 75 /** calculate the variable's distribution parameters (mean and variance) for the bounds specified in the arguments. 87 /** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed 108 * For equations (lhs==rhs), we use the centeredness measure p = min(PHI(lhs'), 1-PHI(lhs'))/max(PHI(lhs'), 1 - PHI(lhs')), 117 int rowinfinitiesdown, /**< the number of variables with infinite bounds to DECREASE activity */ 121 /** update the up- and downscore of a single variable after calculating the impact of branching on a SCIP_RETCODE SCIPincludeBranchruleDistribution(SCIP *scip) SCIP_RETCODE SCIPupdateDistributionScore(SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam) SCIP_Real SCIPcalcCumulativeDistribution(SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value) void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance) SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup) Definition: objbranchrule.h:33 SCIP callable library. |