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