Problem description

The objective of the Ringpacking Problem is to select a minimum number of rectangles of the same size such that a given set of rings can be packed into these rectangles in a non-overlapping way. A ring is characterized by an internal and an external radius. Rings can be put recursively into larger ones or directly into a rectangle. The following picture gives two examples of such packings:

Instead of using a compact noncovex MINLP formulation, we utilize the results from A. Gleixner, S. Maher, B. Mueller, and J. Pedroso that have been presented in ZIB-Report 17-07. Their approach is based on a Dantzig-Wolfe decomposition that can be solved via column generation. The first step is a reformulation which is similar to the classical reformulation for the Cutting Stock Problem, however, featuring nonlinear and nonconvex sub-problems. The purpose of this formulation is to break the symmetry between equivalent rectangles. As a second step, we combine this reformulation with an enumeration scheme for patterns that are characterized by rings packed inside other rings. Such patterns only allow for a one-level recursion and break the symmetry between rings with the same internal and external radius in each rectangle.

More precisely, we introduce an integral variable \(z_{P}\) for each rectangular pattern \(P\) and an integral variable \(z_{C}\) for each circular pattern \(C\). A vector \(P \in \mathbb{Z}_{+}^T\), where \(T\) is the total number of ringtypes, is a rectangular pattern if and only if \(P_t\) many circles with external radius \(R_t\) for each \(t \in \mathcal{T}\) (the set of types) can be packed together into a rectangle. Similarly, a tuple \((t,P)\in \mathcal{T} \times \mathbb{Z}_{+}^T\) is a circular pattern if it is possible to pack \(P_1\) many circles of type \(1\), \(P_2\) many circles of type \(2\), \(\ldots\), \(P_T\) many circles of type \(T\) into a larger ring of type \(t\). Let \(\mathcal{RP}\) and \(\mathcal{CP}\) be the set of all rectangular or circular patterns, respectively, and let \(D_t\) denote the demand of ringtype \(t\).

Then the problem can be formulated as follows:

\[ \begin{align} && \min \sum_{P \in \mathcal{RP}} z_P \quad\,\\ && \text{s.t.} \sum_{C = (t,P) \in \mathcal{CP}} z_C &\ge D_t && \text{ for all } t \in \mathcal{T} \\ && \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} \\ && z_C & \in \mathbb{Z}_{+} && \text{ for all } C \in \mathcal{CP} \\ && z_P & \in \mathbb{Z}_{+} && \text{ for all } P \in \mathcal{RP} \end{align} \]

The objective minimizes the total number of used rectangles. The first constraint ensures that the demand for each ring type is satisfied. The recursive decisions how to place rings into each other are implicitly modeled by the second type of constraints. Each selection of a pattern allows us to choose \(P_t\) circular patterns of the type \((t,P)\). Note that at least one rectangular pattern needs to be selected before circular patterns can be packed. This is true because the largest ring only fits into a rectangular pattern.

Since \(\mathcal{RP}\) can be of exponential size, we are using a column generation approach to solve this problem. We initialize the (master) problem with a set of variables representing a selection of rectangular patterns that are easy to verify. Now, we have to iteratively search for variables representing "better" patterns, i.e., a pattern which reduces the overall cost. Let \(\lambda\) be the non-negative vector of dual multipliers for the recursive constraints after solving the LP relaxation of the restricted master problem for the current set of rectangular patterns. To compute a rectangular pattern with negative reduced cost we solve

\[ \begin{equation} \min_{P \in \mathcal{RP}} \left\{1 - \sum_{t \in \mathcal{T}} \lambda_t P_t\right\}. \end{equation} \]

This problem is NP-hard and can be very difficult to solve. However, even if it cannot be solved to optimality within the given time limit, any solution with negative reduced cost can be used to continue the solving process. In that case, a dual bound of the LP relaxation can also be turned into a valid dual bound of the complete master problem. See Pricing new variables for more details. Also note that the dual bound is invalidated after the first branching step. This means that it is not a typical branch-and-price, but rather a price-and-branch framework.

Another issue with the above formulation is the fact that \(\mathcal{CP}\) can be of exponential size, as well. We try to overcome this by using a column enumeration algorithm to compute all relevant circular patterns. See Enumeration of circular patterns for details.