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