SCIP Doxygen Documentation
Loading...
Searching...
No Matches
xternal_ringpacking.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-2025 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_ringpacking.c
26
* @brief The ringpacking application of SCIP
27
* @author Benjamin Mueller
28
*/
29
30
/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31
32
/**@page RINGPACKING_MAIN Ringpacking
33
* @author Benjamin Mueller
34
*
35
* This application contains a branch-and-price approach for the Ringpacking problem, also known as recursive circle
36
* packing problem, which is realized with the framework \SCIP. Therefore, the following plugins are implemented:
37
*
38
* - a \ref reader_rpa.c "problem reader" which parses the problem out of a file and creates the corresponding problem within \SCIP
39
* - a \ref probdata_rpa.c "(global) problem data structure" which contains all necessary information
40
* - a \ref pricer_rpa.c "pricer" which generates new variables/columns during the search
41
* - a \ref cons_rpa.c "constraint handler" which stores information about which patterns have been verified
42
* - a \ref pattern.c "variable data structure" which provides fundamental functions for handling patterns
43
*
44
* In the following we introduce the problem, explain the use of the reader plugin and pricer plugin.
45
*
46
* -# \subpage RINGPACKING_PROBLEM "Problem description"
47
* -# \subpage RINGPACKING_READER "Parsing the input format and creating the problem"
48
* -# \subpage RINGPACKING_PROBLEMDATA "Main problem data"
49
* -# \subpage RINGPACKING_PRICER "Pricing new variables"
50
* -# \subpage RINGPACKING_ENUMERATION "Enumerating circular patterns"
51
*
52
* Installation
53
* ------------
54
*
55
* See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
56
*/
57
58
/**@page RINGPACKING_PROBLEM Problem description
59
*
60
* The objective of the Ringpacking Problem is to select a minimum number of rectangles of the same size such that a
61
* given set of rings can be packed into these rectangles in a non-overlapping way. A ring is characterized by an
62
* internal and an external radius. Rings can be put recursively into larger ones or directly into a rectangle. The
63
* following picture gives two examples of such packings:
64
*
65
*
66
* <CENTER>
67
* \image html ringpacking.png
68
* </CENTER>
69
*
70
*
71
* Instead of using a compact noncovex MINLP formulation, we utilize the results from A. Gleixner, S. Maher, B. Mueller,
72
* and J. Pedroso that have been presented in <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6449">ZIB-Report 17-07</a>.
73
* Their approach is based on a Dantzig-Wolfe decomposition that can be solved via column generation. The first step
74
* is a reformulation which is similar to the classical reformulation for the Cutting Stock Problem, however, featuring
75
* nonlinear and nonconvex sub-problems. The purpose of this formulation is to break the symmetry between equivalent rectangles.
76
* As a second step, we combine this reformulation with an enumeration scheme for patterns that are characterized by rings
77
* packed inside other rings. Such patterns only allow for a one-level recursion and break the symmetry between rings with the
78
* same internal and external radius in each rectangle.
79
*
80
* More precisely, we introduce an integral variable \f$z_{P}\f$ for each rectangular pattern \f$P\f$ and an integral
81
* variable \f$z_{C}\f$ for each circular pattern \f$C\f$. A vector \f$P \in \mathbb{Z}_{+}^T\f$, where \f$T\f$ is
82
* the total number of ringtypes, is a <b>rectangular pattern</b> if and only if \f$P_t\f$ many circles with external radius
83
* \f$R_t\f$ for each \f$t \in \mathcal{T}\f$ (the set of types) can be packed together into a rectangle. Similarly, a tuple
84
* \f$(t,P)\in \mathcal{T} \times \mathbb{Z}_{+}^T\f$ is a <b>circular pattern</b> if it is possible to pack \f$P_1\f$ many
85
* circles of type \f$1\f$, \f$P_2\f$ many circles of type \f$2\f$, \f$\ldots\f$, \f$P_T\f$ many circles of type \f$T\f$
86
* into a larger ring of type \f$t\f$. Let \f$\mathcal{RP}\f$ and \f$\mathcal{CP}\f$ be the set of all rectangular or
87
* circular patterns, respectively, and let \f$D_t\f$ denote the demand of ringtype \f$t\f$.
88
*
89
* Then the problem can be formulated as follows:
90
*
91
* \f[
92
* \begin{align}
93
* && \min \sum_{P \in \mathcal{RP}} z_P \quad\,\\
94
* && \text{s.t.} \sum_{C = (t,P) \in \mathcal{CP}} z_C &\ge D_t && \text{ for all } t \in \mathcal{T} \\
95
* && \sum_{C = (t,P) \in \mathcal{CP}} z_C &\le \sum_{P \in \mathcal{RP}} P_t \cdot z_P + \sum_{C = (t',P) \in \mathcal{CP}} P_t \cdot z_C && \text{ for all } t \in \mathcal{T} \\
96
* && z_C & \in \mathbb{Z}_{+} && \text{ for all } C \in \mathcal{CP} \\
97
* && z_P & \in \mathbb{Z}_{+} && \text{ for all } P \in \mathcal{RP}
98
* \end{align}
99
* \f]
100
*
101
* The objective minimizes the total number of used rectangles. The first constraint ensures that the demand for each
102
* ring type is satisfied. The recursive decisions how to place rings into each other are implicitly modeled by the
103
* second type of constraints. Each selection of a pattern allows us to choose \f$P_t\f$ circular patterns of the type
104
* \f$(t,P)\f$. Note that at least one rectangular pattern needs to be selected before circular patterns can be packed.
105
* This is true because the largest ring only fits into a rectangular pattern.
106
*
107
* Since \f$\mathcal{RP}\f$ can be of exponential size, we are using a column generation approach to solve this
108
* problem. We initialize the (master) problem with a set of variables representing a selection of rectangular patterns
109
* that are easy to verify. Now, we have to iteratively search for variables representing "better" patterns, i.e.,
110
* a pattern which reduces the overall cost. Let \f$\lambda\f$ be the non-negative vector of dual multipliers for
111
* the recursive constraints after solving the LP relaxation of the restricted master problem for the
112
* current set of rectangular patterns. To compute a rectangular pattern with negative reduced cost we solve
113
*
114
* \f[
115
* \begin{equation}
116
* \min_{P \in \mathcal{RP}} \left\{1 - \sum_{t \in \mathcal{T}} \lambda_t P_t\right\}.
117
* \end{equation}
118
* \f]
119
*
120
* This problem is NP-hard and can be very difficult to solve. However, even if it cannot be solved to optimality within the
121
* given time limit, any solution with negative reduced cost can be used to continue the solving process. In that case, a
122
* dual bound of the LP relaxation can also be turned into a valid dual bound of the complete master problem. See
123
* @ref RINGPACKING_PRICER for more details. Also note that the dual bound is invalidated after the first branching step.
124
* This means that it is not a typical branch-and-price, but rather a <b>price-and-branch</b> framework.
125
*
126
* Another issue with the above formulation is the fact that \f$\mathcal{CP}\f$ can be of exponential size, as well. We try
127
* to overcome this by using a column enumeration algorithm to compute all relevant circular patterns.
128
* See @ref RINGPACKING_ENUMERATION for details.
129
*/
130
131
132
/**@page RINGPACKING_ENUMERATION Enumeration of circular patterns
133
*
134
* Here we describe a column enumeration algorithm that is used to deal with the exponential number of circular patterns.
135
*
136
* The main step of the algorithm is to verify whether a given tuple \f$(t,P)\in \mathcal{T} \times\mathbb{Z}_{+}^T\f$
137
* is in the set \f$\mathcal{CP}\f$ or not. A tuple can be checked by solving the following nonlinear nonconvex
138
* verification problem:
139
*
140
* \f[
141
* \begin{align}
142
* {\left\|{{\begin{pmatrix}x_i\\y_i\end{pmatrix}} - {\begin{pmatrix}x_j\\y_j\end{pmatrix}}}\right\|}_2 \ge R_i + Rj && \text{ for all } i,j \in C: i < j \\
143
* {\left\|{{\begin{pmatrix}x_i\\y_i\end{pmatrix}}}\right\|}_2 \le r_t - R_i && \text{ for all } i \in C \\
144
* x_i, y_i \in \mathbb{R} && \text{ for all } i \in C
145
* \end{align}
146
* \f]
147
*
148
* Here \f$C\f$ is the index set of individual circles, and \f$R_i\f$ the corresponding external radius of a circle \f$i \in
149
* C\f$. The model checks whether all circles can be placed in a non-overlapping way into a ring of type \f$t\in\mathcal{T}\f$.
150
* The first constraints ensure that no two circles overlap, and the second constraints guarantee that all circles are placed
151
* inside a ring of type \f$t\f$.
152
*
153
* Two more steps are taken in order to solve this problem more efficiently. Firstly, symmetry handling constraints are added
154
* to break the large amount of symmetry the formulation contains. Secondly, a dominance relation betwen circular patterns is
155
* introduced. In fact, it is easy to see that some patterns are never needed in an optimal solution, e.g. when at least one
156
* more circle fits. Therefore, some patterns don't have to be verified if certain others have already been (dis)proved to be
157
* feasible. The algorithm enumerates the circular patterns in a way that minimizes the number of verifications that have to
158
* be performed. See <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6449">ZIB-Report 17-07</a>
159
* for more details.
160
*
161
* In addition to all this, a simple greedy heuristic is used to verify simple patterns before actually solving the NLP.
162
*/
163
applications
Ringpacking
doc
xternal_ringpacking.c
© 2002-2025 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.13.2