Scippy

    SCIP

    Solving Constraint Integer Programs

    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-2026 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 */