Scippy

    SCIP

    Solving Constraint Integer Programs

    xternal_binpacking.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_binpacking.c
    26 * @brief The bin packing example of SCIP
    27 * @author Timo Berthold
    28 * @author Stefan Heinz
    29 */
    30
    31/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
    32
    33/**@page BINPACKING_MAIN Binpacking
    34 * @author Timo Berthold
    35 * @author Stefan Heinz
    36 *
    37 * This example contains a branch-and-price approach for the binpacking problem which is realized with the framework
    38 * \SCIP. Therefore, the following plugins are implemented:
    39 *
    40 * - a \ref reader_bpa.c "problem reader" which parses the problem out of file and creates the corresponding problem within \SCIP
    41 * - a \ref probdata_binpacking.c "(global) problem data structure" which contains all necessary information
    42 * - a \ref pricer_binpacking.c "pricer" which generates new variables/columns during the search
    43 * - the \ref branch_ryanfoster.c "Ryan/Foster branching rule"
    44 * - a \ref cons_samediff.c "constraint handler" which handles the branching decisions of the Ryan/Foster branching
    45 * - a \ref vardata_binpacking.c "variable data structure" which stores information for each variable and is needed to perform the Ryan/Foster
    46 * branching
    47 *
    48 * In the following we introduce the problem, explain the use of the reader plugin and pricer plugin. Finally, we
    49 * introduce the Ryan/Foster branching rule and briefly discuss how that specific branching rule is realized within
    50 * the framework \SCIP.
    51 *
    52 * -# @subpage BINPACKING_PROBLEM "Problem description"
    53 * -# @subpage BINPACKING_READER "Parsing the input format and creating the problem"
    54 * -# @subpage BINPACKING_PROBLEMDATA "Main problem data"
    55 * -# @subpage BINPACKING_PRICER "Pricing new variables"
    56 * -# @subpage BINPACKING_BRANCHING "Ryan/Foster branching"
    57 *
    58 * Installation
    59 * ------------
    60 *
    61 * See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
    62 */
    63
    64/**@page BINPACKING_PROBLEM Problem description
    65 *
    66 * The binpacking problem consists of the task to distribute a given set of items \f$ [n] := \{1, \dots, n\}\f$ with
    67 * nonnegative size \f$s_i\f$ to a minimal number of bins, all of the same capacity \f$\kappa\f$. As example consider 9
    68 * items with sizes: 2, 1, 2, 1, 1, 2, 3, 2, and 1 and a bin capacity of \f$\kappa\f$ of 4. The following pictures show
    69 * a feasible solution which needs 5 bins. The minimum number of bins needed for that example is 3.
    70 *
    71 * <CENTER>
    72 * \image html binpacking.png
    73 * </CENTER>
    74 *
    75 * This problem can be formulated as a set covering problem as discussed by Gilmore and Gomory in the following two classical papers:
    76 * - Gilmore P. C., R. E. Gomory: A linear programming approach to the cutting-stock problem. Operations Research 9 (1961): 849-859.
    77 * - Gilmore P. C., R. E. Gomory: A linear programming approach to the cutting-stock problem - Part II. Operations Research 11 (1963): 863-888
    78 *
    79 * We introduce a binary variable \f$x_{S}\f$ for each feasible packing \f$S\f$. A <b>packing</b> \f$S\f$ is an
    80 * assignment vector \f$ \lambda_{S}\in\{0,1\}^n \f$ which states the items belonging to that packing. It is
    81 * <b>feasible</b>, if and only if the total size of the items contained in this assignment is not greater than the
    82 * given capacity \f$\kappa\f$. Let \f$\mathcal{S}\f$ be the set of all feasible packing, this measns:
    83 *
    84 * \f[
    85 * \mathcal{S} := \{S\subseteq [n] \mid \sum_{i:i\in S} s_{i} \leq \kappa \}
    86 * \f]
    87 *
    88 * An integer program can be formulated as follows:
    89 *
    90 * \f[
    91 * \begin{array}[t]{rll}
    92 * \min & \displaystyle \sum_{S \in \mathcal{S}} x_{S} \\
    93 * & \\
    94 * subject \ to & \displaystyle \sum_{S \in \mathcal{S}} (\lambda_{S})_{i}x_{S} \ge 1 & \quad \forall i \in \{1,\dots,n\} \\
    95 * & \\
    96 * & x_{S} \in \{0,1\} & \quad \forall S \in \mathcal{S} \\
    97 * \end{array}
    98 * \f]
    99 *
    100 * This means we are searching for a set of packings such that each item is contained in at least one of the selected
    101 * packings. Since the objective is to minimize the number of used packings, each optimal solution to the above problem
    102 * can be transformed into a solution where each item is packed exactly once with the same cost.
    103 *
    104 *
    105 * Since \f$\mathcal{S}\f$ can be of exponential size, we are using a column generation approach to solve this
    106 * problem. We initialize the (master) problem with a set of \f$ n \f$ variables representing packings of a single item
    107 * per bin. Now, we have to iteratively search for variables representing "better" packings, i.e., a packing pattern
    108 * which reduces the overall cost. For a given solution \f$y^\star\f$ of the (restricted) dual linear program, we have
    109 * to find a variable/packing \f$ \lambda_{S} \f$ for which the reduced costs is negative. This means:
    110 *
    111 * \f[
    112 * c_{S} - \sum_{i=0}^n (\lambda_S)_i y_i^\star < 0.
    113 * \f]
    114 *
    115 * Since all variables \f$ \lambda_{S} \f$ have an objective coefficient \f$ c_{S} = 1 \f$ the above condition is
    116 * equivalent to
    117 *
    118 * \f[
    119 * \sum_{i=0}^n (\lambda_S)_i y_i^\star > 1.
    120 * \f]
    121 *
    122 *
    123 * To find such a variable/packing we solve the following integer program:
    124 *
    125 * \f[
    126 * \begin{array}[t]{rll}
    127 * \max & \displaystyle \sum_{i=1}^n (\lambda_S)_i y^\star_i\\
    128 * & \\
    129 * subject \ to & \displaystyle \sum_{i=0}^n (\lambda_S)_i s_i \leq \kappa \\
    130 * & \\
    131 * & (\lambda_S)_i \in \{0,1\} & \quad \forall i \in \{ 1, \dots , n \} \\
    132 * \end{array}
    133 * \f]
    134 *
    135 * where \f$ (\lambda_S)_i \f$ for \f$i\in\{1,\dots,n\}\f$ are binary variables and \f$y^\star_i\f$ given by the dual
    136 * solution of the restricted master problem.
    137 *
    138 * The above problem is a knapsack problem which can be solved via dynamic programming or by solving the above integer
    139 * program. In this example we implemented a pricer which solves the integer program.
    140 *
    141 */
    142
    143