SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-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_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