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
*/
examples
SCFLP
doc
xternal_scflp.c
© 2002-2024 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.12.0