1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file branch_distribution.h 26 * @ingroup BRANCHINGRULES 27 * @brief probability based branching rule based on an article by J. Pryor and J.W. Chinneck 28 * @author Gregor Hendel 29 * 30 * The distribution branching rule selects a variable based on its impact on row activity distributions. More formally, 31 * 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 32 * (finite) lower and upper bound, respectively, of the \f$ i \f$-th variable \f$x_i\f$. 33 * Viewing every variable \f$x_i \f$ as (continuously) uniformly distributed within its bounds, we can approximately 34 * 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$ 35 * 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 36 * continuous and \f$ \sigma_i^2 = \frac{(u_i - l_i + 1)^2 - 1}{12}\f$ for discrete variables. 37 * With these two parameters, we can calculate the probability to satisfy the row in terms of the cumulative distribution 38 * of the standard normal distribution: \f$ P(a(x) \leq b) = \Phi(\frac{b - \mu}{\sigma})\f$. 39 * 40 * The impact of a variable on the probability to satisfy a constraint after branching can be estimated by altering 41 * the variable contribution to the sums described above. In order to keep the tree size small, 42 * variables are preferred which decrease the probability 43 * to satisfy a row because it is more likely to create infeasible subproblems. 44 * 45 * The selection of the branching variable is subject to the parameter @p scoreparam. For both branching directions, 46 * an individual score is calculated. Available options for scoring methods are: 47 * - @b d: select a branching variable with largest difference in satisfaction probability after branching 48 * - @b l: lowest cumulative probability amongst all variables on all rows (after branching). 49 * - @b h: highest cumulative probability amongst all variables on all rows (after branching). 50 * - @b v: highest number of votes for lowering row probability for all rows a variable appears in. 51 * - @b w: highest number of votes for increasing row probability for all rows a variable appears in. 52 * 53 * If the parameter @p usescipscore is set to @a TRUE, a single branching score is calculated from the respective 54 * up and down scores as defined by the SCIP branching score function (see advanced branching parameter @p scorefunc), 55 * otherwise, the variable with the single highest score is selected, and the maximizing direction is assigned 56 * higher branching priority. 57 * 58 * The original idea of probability based branching schemes appeared in: 59 * 60 * J. Pryor and J.W. Chinneck:@n 61 * Faster Integer-Feasibility in Mixed-Integer Linear Programs by Branching to Force Change@n 62 * Computers and Operations Research, vol. 38, 2011, p. 1143–1152@n 63 * (http://www.sce.carleton.ca/faculty/chinneck/docs/PryorChinneck.pdf) 64 */ 65 66 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 67 68 #ifndef __SCIP_BRANCH_DISTRIBUTION_H__ 69 #define __SCIP_BRANCH_DISTRIBUTION_H__ 70 71 72 #include "scip/def.h" 73 #include "scip/type_lp.h" 74 #include "scip/type_retcode.h" 75 #include "scip/type_scip.h" 76 #include "scip/type_var.h" 77 78 #ifdef __cplusplus 79 extern "C" { 80 #endif 81 82 /** creates the distribution branching rule and includes it in SCIP 83 * 84 * @ingroup BranchingRuleIncludes 85 */ 86 SCIP_EXPORT 87 SCIP_RETCODE SCIPincludeBranchruleDistribution( 88 SCIP* scip /**< SCIP data structure */ 89 ); 90 91 /**@addtogroup BRANCHINGRULES 92 * 93 * @{ 94 */ 95 96 /** calculate the variable's distribution parameters (mean and variance) for the bounds specified in the arguments. 97 * special treatment of infinite bounds necessary */ 98 SCIP_EXPORT 99 void SCIPvarCalcDistributionParameters( 100 SCIP* scip, /**< SCIP data structure */ 101 SCIP_Real varlb, /**< variable lower bound */ 102 SCIP_Real varub, /**< variable upper bound */ 103 SCIP_VARTYPE vartype, /**< type of the variable */ 104 SCIP_Real* mean, /**< pointer to store mean value */ 105 SCIP_Real* variance /**< pointer to store the variance of the variable uniform distribution */ 106 ); 107 108 /** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed 109 * random variable x takes a value between -infinity and parameter \p value. 110 * 111 * The distribution is given by the respective mean and deviation. This implementation 112 * uses the error function erf(). 113 */ 114 SCIP_EXPORT 115 SCIP_Real SCIPcalcCumulativeDistribution( 116 SCIP* scip, /**< current SCIP */ 117 SCIP_Real mean, /**< the mean value of the distribution */ 118 SCIP_Real variance, /**< the square of the deviation of the distribution */ 119 SCIP_Real value /**< the upper limit of the calculated distribution integral */ 120 ); 121 122 /** calculates the probability of satisfying an LP-row under the assumption 123 * of uniformly distributed variable values. 124 * 125 * For inequalities, we use the cumulative distribution function of the standard normal 126 * distribution PHI(rhs - mu/sqrt(sigma2)) to calculate the probability 127 * for a right hand side row with mean activity mu and variance sigma2 to be satisfied. 128 * Similarly, 1 - PHI(lhs - mu/sqrt(sigma2)) is the probability to satisfy a left hand side row. 129 * For equations (lhs==rhs), we use the centeredness measure p = min(PHI(lhs'), 1-PHI(lhs'))/max(PHI(lhs'), 1 - PHI(lhs')), 130 * where lhs' = lhs - mu / sqrt(sigma2). 131 */ 132 SCIP_EXPORT 133 SCIP_Real SCIProwCalcProbability( 134 SCIP* scip, /**< current scip */ 135 SCIP_ROW* row, /**< the row */ 136 SCIP_Real mu, /**< the mean value of the row distribution */ 137 SCIP_Real sigma2, /**< the variance of the row distribution */ 138 int rowinfinitiesdown, /**< the number of variables with infinite bounds to DECREASE activity */ 139 int rowinfinitiesup /**< the number of variables with infinite bounds to INCREASE activity */ 140 ); 141 142 /** update the up- and downscore of a single variable after calculating the impact of branching on a 143 * particular row, depending on the chosen score parameter 144 */ 145 SCIP_EXPORT 146 SCIP_RETCODE SCIPupdateDistributionScore( 147 SCIP* scip, /**< current SCIP pointer */ 148 SCIP_Real currentprob, /**< the current probability */ 149 SCIP_Real newprobup, /**< the new probability if branched upwards */ 150 SCIP_Real newprobdown, /**< the new probability if branched downwards */ 151 SCIP_Real* upscore, /**< pointer to store the new score for branching up */ 152 SCIP_Real* downscore, /**< pointer to store the new score for branching down */ 153 char scoreparam /**< parameter to determine the way the score is calculated */ 154 ); 155 156 /** @} */ 157 158 #ifdef __cplusplus 159 } 160 #endif 161 162 #endif 163