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