SCIP

Solving Constraint Integer Programs

 branch_distribution.h Go to the documentation of this file. 1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2015 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15  16 /**@file branch_distribution.h 17  * @ingroup BRANCHINGRULES 18  * @brief probability based branching rule based on an article by J. Pryor and J.W. Chinneck 19  * @author Gregor Hendel 20  * 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 23  * (finite) lower and upper bound, respectively, of the \f$i \f$-th variable \f$x_i\f$. 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 27  * continuous and \f$\sigma_i^2 = \frac{(u_i - l_i + 1)^2 - 1}{12}\f$ for discrete variables. 28  * With these two parameters, we can calculate the probability to satisfy the row in terms of the cumulative distribution 29  * of the standard normal distribution: \f$P(a(x) \leq b) = \Phi(\frac{b - \mu}{\sigma})\f$. 30  * 31  * The impact of a variable on the probability to satisfy a constraint after branching can be estimated by altering 32  * the variable contribution to the sums described above. In order to keep the tree size small, 33  * variables are preferred which decrease the probability 34  * to satisfy a row because it is more likely to create infeasible subproblems. 35  * 36  * The selection of the branching variable is subject to the parameter @p scoreparam. For both branching directions, 37  * an individual score is calculated. Available options for scoring methods are: 38  * - @b d: select a branching variable with largest difference in satisfaction probability after branching 39  * - @b l: lowest cumulative probability amongst all variables on all rows (after branching). 40  * - @b h: highest cumulative probability amongst all variables on all rows (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. 43  * 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 47  * higher branching priority. 48  * 49  * The original idea of probability based branching schemes appeared in: 50  * 51  * J. Pryor and J.W. Chinneck:@n 52  * Faster Integer-Feasibility in Mixed-Integer Linear Programs by Branching to Force Change@n 53  * Computers and Operations Research, vol. 38, 2011, p. 1143–1152@n 54  * (http://www.sce.carleton.ca/faculty/chinneck/docs/PryorChinneck.pdf) 55  */ 56  57 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 58  59 #ifndef __SCIP_BRANCH_DISTRIBUTION_H__ 60 #define __SCIP_BRANCH_DISTRIBUTION_H__ 61  62  63 #include "scip/scip.h" 64  65 #ifdef __cplusplus 66 extern "C" { 67 #endif 68  69 /** creates the distribution branching rule and includes it in SCIP */ 70 extern 72  SCIP* scip /**< SCIP data structure */ 73  ); 74  75 /** calculate the variable's distribution parameters (mean and variance) for the bounds specified in the arguments. 76  * special treatment of infinite bounds necessary */ 77 extern 79  SCIP* scip, /**< SCIP data structure */ 80  SCIP_Real varlb, /**< variable lower bound */ 81  SCIP_Real varub, /**< variable upper bound */ 82  SCIP_VARTYPE vartype, /**< type of the variable */ 83  SCIP_Real* mean, /**< pointer to store mean value */ 84  SCIP_Real* variance /**< pointer to store the variance of the variable uniform distribution */ 85  ); 86  87 /** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed 88  * random variable x takes a value between -infinity and parameter \p value. 89  * 90  * The distribution is given by the respective mean and deviation. This implementation 91  * uses the error function erf(). 92  */ 93 extern 95  SCIP* scip, /**< current SCIP */ 96  SCIP_Real mean, /**< the mean value of the distribution */ 97  SCIP_Real variance, /**< the square of the deviation of the distribution */ 98  SCIP_Real value /**< the upper limit of the calculated distribution integral */ 99  ); 100  101 /** calculates the probability of satisfying an LP-row under the assumption 102  * of uniformly distributed variable values. 103  * 104  * For inequalities, we use the cumulative distribution function of the standard normal 105  * distribution PHI(rhs - mu/sqrt(sigma2)) to calculate the probability 106  * for a right hand side row with mean activity mu and variance sigma2 to be satisfied. 107  * Similarly, 1 - PHI(lhs - mu/sqrt(sigma2)) is the probability to satisfy a left hand side row. 108  * For equations (lhs==rhs), we use the centeredness measure p = min(PHI(lhs'), 1-PHI(lhs'))/max(PHI(lhs'), 1 - PHI(lhs')), 109  * where lhs' = lhs - mu / sqrt(sigma2). 110  */ 111 extern 113  SCIP* scip, /**< current scip */ 114  SCIP_ROW* row, /**< the row */ 115  SCIP_Real mu, /**< the mean value of the row distribution */ 116  SCIP_Real sigma2, /**< the variance of the row distribution */ 117  int rowinfinitiesdown, /**< the number of variables with infinite bounds to DECREASE activity */ 118  int rowinfinitiesup /**< the number of variables with infinite bounds to INCREASE activity */ 119  ); 120  121 /** update the up- and downscore of a single variable after calculating the impact of branching on a 122  * particular row, depending on the chosen score parameter 123  */ 124 extern 126  SCIP* scip, /**< current SCIP pointer */ 127  SCIP_Real currentprob, /**< the current probability */ 128  SCIP_Real newprobup, /**< the new probability if branched upwards */ 129  SCIP_Real newprobdown, /**< the new probability if branched downwards */ 130  SCIP_Real* upscore, /**< pointer to store the new score for branching up */ 131  SCIP_Real* downscore, /**< pointer to store the new score for branching down */ 132  char scoreparam /**< parameter to determine the way the score is calculated */ 133  ); 134  135 #ifdef __cplusplus 136 } 137 #endif 138  139 #endif SCIPincludeBranchruleDistributionSCIP_RETCODE SCIPincludeBranchruleDistribution(SCIP *scip) SCIP_ROWstruct SCIP_Row SCIP_ROWDefinition: type_lp.h:93 SCIP_RETCODEenum SCIP_Retcode SCIP_RETCODEDefinition: type_retcode.h:53 SCIPupdateDistributionScoreSCIP_RETCODE SCIPupdateDistributionScore(SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam) SCIPcalcCumulativeDistributionSCIP_Real SCIPcalcCumulativeDistribution(SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value) SCIPvarCalcDistributionParametersvoid SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance) SCIPstruct Scip SCIPDefinition: type_scip.h:30 SCIProwCalcProbabilitySCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup) SCIP_Real#define SCIP_RealDefinition: def.h:124 SCIP_VARTYPEenum SCIP_Vartype SCIP_VARTYPEDefinition: type_var.h:58 scip.hSCIP callable library. Generated on Wed Jul 22 2015 for SCIP Doxygen Documentation by doxygen (1.8.6) © 2024 by Zuse Institute Berlin (ZIB), Imprint designed with Bootstrap