SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
xternal_scflp.c
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-2024 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 xternal_scflp.c
26 * @brief main document page
27 * @author Stephen J. Maher
28 */
29
30/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31
32/**@page SCFLP_MAIN Stochastic Capacitated Facility Location Problem
33 * @version 0.9
34 * @author Stephen J. Maher
35
36 * This is an example of using the Benders' decomposition framework of SCIP to solve the stochastic capacitated facility
37 * location problem (abbreviated to SCFLP). The instances used for this problem are taken from the OR-Library CAP
38 * instances. These instances describe the deterministic capacitated facility location problem. The customer demands of
39 * the deterministic problem are used as the mean of the normal distribution in the stochastic program.
40 *
41 * To use the Benders' decomposition framework to solve the SCFLP instances requires the implementation of two plugins:
42 *
43 * - a \ref reader_scflp.c "problem reader" which parses the data from the CAP instance files and provides it to the
44 * probdata plugin in a convenient format to build the problem within \SCIP.
45 * - a \ref probdata_scflp.c "problem data structure" which builds the problem and stores the global information. The
46 * storage of global information is not absolutely necessary in this example, but it can be useful in post processing
47 * of the solutions and checking their correctness.
48 *
49 * The SCFLP example formulates the problem as the determinstic equivalent, which can be solved directly by SCIP and by
50 * Benders' decomposition. Initially, we will describe how to build the deterministic equivalent problem. Second, we
51 * will describe how to build the problem so that the Benders' decomposition framework can be used.
52 *
53 * -# @subpage SCFLP_PROBLEM "Problem description"
54 * -# @subpage SCFLP_READER "Parsing the input format"
55 * -# @subpage SCFLP_SOLVEPROB "Solving the deterministic equivalent using SCIP"
56 * - @subpage SCFLP_DETEQUIV "Directly as a monolithic MIP"
57 * - @subpage SCFLP_BENDERS "Applying Benders' decomposition"
58 *
59 * Installation
60 * ------------
61 *
62 * See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
63 */
64
65/**@page SCFLP_PROBLEM Problem description
66 *
67 * In the following we describe the CIP model that we use: both the monolithic mixed integer program and the decomposed
68 * problem (using Benders' decomposition).
69 *
70 * Given: a set of facilities \f$ I \f$ and a set of customers \f$ J \f$. The set of scenarios is given by \f$ S \f$,
71 * which are defined by a set of different customer demands.
72 *
73 * Task: Find the minimum cost facilities to open such that the customer demand can be satisfied in all scenarios.
74 *
75 * Variables:
76 * - \f$ x_i \in \{0,1\} \quad \forall i \in I \f$:
77 * - \f$ x_i = 1 \f$ if facility \f$ i \f$ is opened.
78 * - \f$ y^{s}_{ij} \ge 0 \quad \forall i \in I, \forall j \in J, \forall s \in S \f$
79 * - \f$ y^{s}_{ij} \f$ is the level of demand for customer \f$ j \f$ satisfied by facility \f$ i \f$ in scenario
80 * \f$ s \f$.
81 *
82 * Parameters:
83 * - \f$ f_i \f$ the fixed cost for opening facility \f$ i \f$,
84 * - \f$ q_{ij} \f$ the cost of servicing customer \f$ j \f$ from facility \f$ i \f$,
85 * - \f$ \lambda^{s}_{j} \f$ the demand of customer \f$ j \f$ in scenario \f$ s \f$,
86 * - \f$ k_i \f$ the capacity of facility \f$ i \f$.
87 *
88 * @section SCFLP_DETEQUIVMODEL The deterministic equivalent
89 *
90 * The deterministic equivalent can be formulated as:
91 *
92 * \f[
93 * \begin{array}[t]{rll}
94 * \min & \displaystyle \sum_{i \in I} f_{i} x_{i} + \frac{1}{|S|}\sum_{s \in S}\sum_{i \in I}\sum_{j \in J}q_{ij}y^{s}_{ij} \\
95 * & \\
96 * subject \ to & \displaystyle \sum_{i \in I} y^{s}_{ij} \ge \lambda^{s}_{j} & \quad \forall j \in J, \forall s \in S \\
97 * & \\
98 * & \displaystyle \sum_{j \in J} y^{s}_{ij} \le k_{i}x_{i} & \quad \forall i \in I, \forall s \in S \\
99 * & \\
100 * & \displaystyle \sum_{i \in I} k_{i}x_{i} \ge \max_{s \in S}\sum_{j \in J}\lambda^{s}_{j} & \\
101 * & \\
102 * & \displaystyle x_{i} \in \{0, 1\} & \quad \forall i \in I \\
103 * & \\
104 * & \displaystyle y^{s}_{ij} \ge 0 & \quad \forall i \in I, \forall j \in J, \forall s \in S \\
105 * \end{array}
106 * \f]
107 *
108 * It can be seen that as the number of scenarios increases, the size of the deterministic equivalent increases
109 * significantly. For large numbers of scenarios, the resulting deterministic equivalent can in intractable. This
110 * limitation can be addressed by applying decomposition techniques. In this example, Benders' decomposition is applied
111 * to solve the stochastic capacitated facility location problem.
112 *
113 * @section SCFLP_BENDERSMODEL Applying Benders' decomposition to the SCFLP
114 *
115 * The application of Benders' decomposition forms a master problem, consisting of only the facility location variables,
116 * and a subproblem for each scenario, consisting of the customer servicing variables for the given secnario.
117 *
118 * The master problem is given by:
119 *
120 * \f[
121 * \begin{array}[t]{rll}
122 * \min & \displaystyle \sum_{i \in I} f_{i} x_{i} + \frac{1}{|S|}\sum_{s \in S}\varphi^{s} \\
123 * & \\
124 * subject \ to & \displaystyle \sum_{i \in I} k_{i}x_{i} \ge \max_{s \in S}\sum_{j \in J}\lambda^{s}_{j} & \\
125 * & \\
126 * & \displaystyle \varphi^{s} \geq \sum_{j \in J}\lambda^{s}_{j}u^{p}_{j} + \sum_{i \in I}k_{i}x_{i}v^{p}_{i} & \quad \forall s \in S, \forall p \in P^{s} \\
127 * & \\
128 * & \displaystyle 0 \geq \sum_{j \in J}\lambda^{s}_{j}u^{r}_{j} + \sum_{i \in I}k_{i}x_{i}v^{r}_{i} & \quad \forall s \in S, \forall r \in R^{s} \\
129 * & \\
130 * & \displaystyle x_{i} \in \{0, 1\} & \quad \forall i \in I \\
131 * & \\
132 * & \displaystyle \varphi^{s} \geq 0 & \quad \forall s \in S \\
133 * \end{array}
134 * \f]
135 *
136 * where \f$ \varphi^{s} \f$ is the auxiliary variable for each scenario \f$ s \f$ that is an underestimator of the
137 * optimal subproblem objective function value. The second and third constraint of the master problem are the Benders'
138* optimality and feasibility cuts. Given a solution to the master problem, an optimality cut for scenario \f$s\f$ is
139* generated from the optimal dual solution to the corresponding subproblem. Similarly, if the solution to the master
140* problem induces an infeasibl instance of subproblem \f$s\f$, then the resulting dual ray is used to generate a
141* feasibility cut.
142 *
143 * The subproblem for scenario \f$ s \f$ that are solved to generate optimality and feasibility cuts are:
144 *
145 * \f[
146 * \begin{array}[t]{rll}
147 * z^{s}(\bar{x}) = \min & \displaystyle \sum_{i \in I}\sum_{j \in J}q_{ij}y^{s}_{ij} \\
148 * & \\
149 * subject \ to & \displaystyle \sum_{i \in I} y^{s}_{ij} \ge \lambda^{s}_{j} & \quad \forall j \in J \\
150 * & \\
151 * & \displaystyle \sum_{j \in J} y^{s}_{ij} \le k_{i}\bar{x}_{i} & \quad \forall i \in I \\
152 * & \\
153 * & \displaystyle y^{s}_{ij} \ge 0 & \quad \forall i \in I, \forall j \in J \\
154 * \end{array}
155 * \f]
156 *
157 * The solution \f$\bar{x}\f$ is the candidate solution that is verified by solving the subproblem. As explained above,
158 * if the subproblem is infeasible, then the corresponding dual ray is used to generate a Benders' feasibility cut. If
159 * the subproblem is optimal and \f$ z^{s}(\bar{x}) > \varphi^{s} \f$, then an optimality cut is generated from the
160 * corresponding dual solution. If \f$ z^{s}(\bar{x}) \le \varphi^{s} \f$, then the subproblem is optimal for the given
161 * solution \f$ \bar{x} \f$. If \f$ z^{s}(\bar{x}) > \varphi^{s} \f$ for all scenario subproblems, then \f$ \bar{x} \f$
162 * is the optimal solution to the original problem.
163 */