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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
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/def.h"
64 #include "scip/type_lp.h"
65 #include "scip/type_retcode.h"
66 #include "scip/type_scip.h"
67 #include "scip/type_var.h"
68
69 #ifdef __cplusplus
70 extern "C" {
71 #endif
72
73 /** creates the distribution branching rule and includes it in SCIP
74  *
75  * @ingroup BranchingRuleIncludes
76  */
79  SCIP* scip /**< SCIP data structure */
80  );
81
83  *
84  * @{
85  */
86
87 /** calculate the variable's distribution parameters (mean and variance) for the bounds specified in the arguments.
88  * special treatment of infinite bounds necessary */
91  SCIP* scip, /**< SCIP data structure */
92  SCIP_Real varlb, /**< variable lower bound */
93  SCIP_Real varub, /**< variable upper bound */
94  SCIP_VARTYPE vartype, /**< type of the variable */
95  SCIP_Real* mean, /**< pointer to store mean value */
96  SCIP_Real* variance /**< pointer to store the variance of the variable uniform distribution */
97  );
98
99 /** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed
100  * random variable x takes a value between -infinity and parameter \p value.
101  *
102  * The distribution is given by the respective mean and deviation. This implementation
103  * uses the error function erf().
104  */
107  SCIP* scip, /**< current SCIP */
108  SCIP_Real mean, /**< the mean value of the distribution */
109  SCIP_Real variance, /**< the square of the deviation of the distribution */
110  SCIP_Real value /**< the upper limit of the calculated distribution integral */
111  );
112
113 /** calculates the probability of satisfying an LP-row under the assumption
114  * of uniformly distributed variable values.
115  *
116  * For inequalities, we use the cumulative distribution function of the standard normal
117  * distribution PHI(rhs - mu/sqrt(sigma2)) to calculate the probability
118  * for a right hand side row with mean activity mu and variance sigma2 to be satisfied.
119  * Similarly, 1 - PHI(lhs - mu/sqrt(sigma2)) is the probability to satisfy a left hand side row.
120  * For equations (lhs==rhs), we use the centeredness measure p = min(PHI(lhs'), 1-PHI(lhs'))/max(PHI(lhs'), 1 - PHI(lhs')),
121  * where lhs' = lhs - mu / sqrt(sigma2).
122  */
125  SCIP* scip, /**< current scip */
126  SCIP_ROW* row, /**< the row */
127  SCIP_Real mu, /**< the mean value of the row distribution */
128  SCIP_Real sigma2, /**< the variance of the row distribution */
129  int rowinfinitiesdown, /**< the number of variables with infinite bounds to DECREASE activity */
130  int rowinfinitiesup /**< the number of variables with infinite bounds to INCREASE activity */
131  );
132
133 /** update the up- and downscore of a single variable after calculating the impact of branching on a
134  * particular row, depending on the chosen score parameter
135  */
138  SCIP* scip, /**< current SCIP pointer */
139  SCIP_Real currentprob, /**< the current probability */
140  SCIP_Real newprobup, /**< the new probability if branched upwards */
141  SCIP_Real newprobdown, /**< the new probability if branched downwards */
142  SCIP_Real* upscore, /**< pointer to store the new score for branching up */
143  SCIP_Real* downscore, /**< pointer to store the new score for branching down */
144  char scoreparam /**< parameter to determine the way the score is calculated */
145  );
146
147 /** @} */
148
149 #ifdef __cplusplus
150 }
151 #endif
152
153 #endif
SCIP_EXPORT void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
SCIP_EXPORT SCIP_RETCODE SCIPincludeBranchruleDistribution(SCIP *scip)
#define SCIP_EXPORT
Definition: def.h:100
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for return codes for SCIP methods
type definitions for LP management
SCIP_EXPORT SCIP_RETCODE SCIPupdateDistributionScore(SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
type definitions for SCIP&#39;s main datastructure
type definitions for problem variables
SCIP_EXPORT SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
SCIP_EXPORT SCIP_Real SCIPcalcCumulativeDistribution(SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value)
#define SCIP_Real
Definition: def.h:163
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:60
common defines and data types used in all packages of SCIP