Scippy

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-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
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
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
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
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
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
void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for return codes for SCIP methods
type definitions for LP management
SCIP_Real SCIPcalcCumulativeDistribution(SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value)
type definitions for SCIP&#39;s main datastructure
type definitions for problem variables
SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
#define SCIP_Real
Definition: def.h:186
SCIP_RETCODE SCIPupdateDistributionScore(SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:73
common defines and data types used in all packages of SCIP
SCIP_RETCODE SCIPincludeBranchruleDistribution(SCIP *scip)