1 Introduction

In this paper, we consider the two-dimensional Strip Packing Problem (SPP) with rectangular items. Let a set \(I:=\{1,\ldots , n \}\) of non-rotatable rectangles \(R_i\) (items) of width \(w_i \le 1\) and height \(h_i \le 1\) be given. The items have to be packed into a strip of width 1 and minimal height OPT such that the items do not overlap each other.

A lot of lower bounds are known for this problem, but for most of them the exact absolute worst-case performance ratio, which is the supremum over all instances of the fraction of the optimal value and the lower bound, is unknown. To reduce the gap between a proven upper bound of the absolute worst-case performance ratio and the performance ratio of an instance having maximal ratio known so far, it is necessary to decrease the theoretical upper bound or to find instances with greater performance ratio.

In the following, we introduce a new approach to compute such worst-case instances. For several lower bounds, we show how to model this issue as an optimization problem which maximizes the performance ratio within a subset of SPP instances. In this way, we obtain the absolute worst-case performance ratio of these lower bounds for the considered subsets.

2 Modeling Lower Bounds for the SPP

In this paper, we consider two lower bounds: (binary) horizontal bar relaxation and contiguous (binary) horizontal bar relaxation [1]. We show how the optimization problems addressed above can be modeled. Since we aim to maximize the absolute worst-case performance ratio which is a fraction, we linearize this objective function by fixing the optimal value and minimizing the height of the lower bound. For our models we assume that all items can be packed using a strip height of at most 1, i.e., \(OPT \le 1\) holds. To ensure that this condition is fulfilled, our model contains a Padberg-type model [2]. The second part of our model describes the considered lower bound. Hence, we aim to minimize the height of the lower bound solution depending on the widths and heights of the items.

2.1 Modeling an Optimal Pattern

The main issue of our approach is the managing of the optimal value of the SPP instance which results by minimization and which should be maximized in comparison to the lower bound at the same time. On the one hand, by definition of the SPP, we search for a feasible pattern with minimal value but we also try to get an instance with lower bound as small as possible. So, in order to get a large absolute worst-case performance ratio the optimal value should be maximized with respect to the considered instance set. To resolve this issue, we fix the optimal value and iterate over all possible patterns to provide the optimal solution, that means, the height of the considered feasible pattern has to be 1 and all other patterns are either infeasible or have height at least 1. Obviously, any particular pattern can be characterized by the relative positions of each pair of items (left, right, above, below). Regarding symmetry and permutation aspects, we have only 4 different patterns with \(n=3\) items (Fig. 1).

Fig. 1
figure 1

Possible patterns of 3 items

Full size image

The pattern which should be the optimal pattern is called current pattern. For the current pattern we have to guarantee that this pattern is feasible and has height of at least 1. To model the feasibility of a current pattern, we consider maximal subsets of items which are placed next to each other in this pattern. These subsets are called horizontal slices of the considered pattern. Obviously, the current pattern is only feasible if the total width of each horizontal slice of this pattern does not exceed the width of the strip. Analogously to the horizontal slices, we denote the maximal subsets of items which are placed above each other in the considered pattern as vertical slices. To ensure that the current pattern has height of at least 1, we have to enforce that the total height of at least one vertical slice of this pattern is at least 1.

To model these conditions, we introduce two binary variables \(x_A\) and \(y_A\) for each possible subset \(A \in \mathscr {P}_n\) of items where \(\mathscr {P}_n\) denotes the set of all subsets of \(\{1,\ldots ,n\}\) with at least two elements. (Note that singletons are not meaningful in our approach.) These variables belong to the horizontal and vertical slices which coincide with the corresponding subsets of items. Since \(x_A\) and \(y_A\) indicate whether the total width or the total height of item set A exceeds the respective boundary of the strip, we apply the following inequalities with a small \(\varepsilon > 0\):

$$\begin{aligned} (1-x_A)*W + \sum \limits _{i \in A} w_i \ge W+ \varepsilon \quad&\text{ for } \text{ all } A \in \mathscr {P}_n, \end{aligned}$$
(1)
$$\begin{aligned} (1-y_A)*1 + \sum \limits _{i \in A} h_i \ge 1 \quad&\text{ for } \text{ all } A \in \mathscr {P}_n. \end{aligned}$$
(2)

In the first inequality, if \(x_A=1\), then the total width of the items of A has to exceed the strip width, otherwise the horizontal slice can be feasible or not. Analogously, if \(y_A=1\), the second inequality ensures that the total height of the items of A is at least 1. Let CP denote the current pattern. Furthermore, let HS(P) and VS(P) denote the set of horizontal and vertical slices of a pattern P, respectively. Then we model the feasibility of CP by demanding the following inequalities:

$$\begin{aligned} \sum \limits _{i \in A} w_i \le W \quad \text{ for } \text{ all } A \in HS(CP) \cap \mathscr {P}_n. \end{aligned}$$
(3)

Note that these inequalities imply

$$\begin{aligned} x_A=0\quad \text{ for } \text{ all } A \in HS(CP) \cap \mathscr {P}_n. \end{aligned}$$

Moreover we ensure that the height of the current pattern is at least 1 by using the following inequality:

$$\begin{aligned} \sum \limits _{A \in VS(CP) \cap \mathscr {P}_n} y_A \ge 1. \end{aligned}$$
(4)

Note that this inequality leads to an infeasible model for that pattern, where all items are packed next to each other (pattern 1 in Fig. 1). But this is not relevant, since the optimal value of the lower bound is equal to 1 in this case. Summarizing the usage of all inequalities (1)–(4) within the model ensures that the current pattern is feasible and has height of at least 1. However, We still have to guarantee that no other pattern has a height less than 1.

2.2 Other Patterns

To ensure that no other feasible pattern gives a better solution than the current pattern CP, we need to add appropriate inequalities for each other pattern. Let OP be any other pattern. Then, to guarantee that pattern OP is not a better feasible pattern than CP, we have to enforce that either OP is infeasible or that it requires a strip height of at least 1. This is modeled by the following inequality:

$$\begin{aligned} \sum \limits _{A \in HS(OP) \cap \mathscr {P}_n} x_A + \sum \limits _{B \in VS(OP) \cap \mathscr {P}_n} y_B \ge 1. \end{aligned}$$
(5)

Adding this inequality for each other pattern we ensure that the current pattern becomes an optimal pattern. Since the height of CP is enforced to be at least 1, now we can minimize the value of the considered relaxation in order to find an instance with a maximal absolute worst case performance ratio.

Since the whole problem is too complex, we consider particular subsets of instances defined as follows: The maximum number of original rectangular items of size \(w_i \times h_i\) in the instance is restricted by a given number N. Clearly, the variables \(w_i\) and \(h_i\), \(i \in I = \{1,\ldots ,N\}\), have to fulfill the constraints

$$\begin{aligned} \varepsilon \le w_i \le 1, \quad&i \in I, \end{aligned}$$
(6)
$$\begin{aligned} 0 \le h_i \le 1, \quad&i \in I. \end{aligned}$$
(7)

Let \((x_i,y_i)\), \(i \in I\), denote the allocation point (lower left corner) of item i, and let \(u_{ij}\) and \(v_{ij}\), \(i,j \in I\), \(i \ne j\), be binary variables (according to [2]) to characterize the mutual position of items i and j in the pattern, then the feasibility of the instance is enforced by

$$\begin{aligned} 0 \le x_i \le 1-w_i, \quad&i \in I, \end{aligned}$$
(8)
$$\begin{aligned} 0 \le y_i \le 1-h_i, \quad&i \in I, \end{aligned}$$
(9)
$$\begin{aligned} x_i + w_i \le x_j +1-u_{ij}, \quad&i , j \in I, \quad i \ne j, \end{aligned}$$
(10)
$$\begin{aligned} y_i + h_i \le y_j +1-v_{ij}, \quad&i , j \in I, \quad i \ne j, \end{aligned}$$
(11)
$$\begin{aligned} u_{ij}+u_{ji}+v_{ij}+v_{ji}=1, \quad&i , j \in I, \quad i \ne j. \end{aligned}$$
(12)

According to the horizontal (contiguous) bar relaxation, any item is partitioned into s item parts of size \(w_i \times h_{ik}\), \(k \in K = \{1,\ldots ,s\}\), by horizontal cuts. Naturally, we have the constraints

$$\begin{aligned} 0 \le h_{ik}, \quad&i \in I, \quad \ k \in K, \end{aligned}$$
(13)
$$\begin{aligned} \sum \limits _{k=1}^s h_{ik}=h_i , \quad&i \in I. \end{aligned}$$
(14)

To model the feasibility of the solution related to the bound, let \((x_{ik},y_{ik})\), \(i \in I\), \(k \in K\), denote the allocation point of item part (i, k). Moreover, let \(u_{ikjl}\) and \(v_{ikjl}\), \(i,j \in I\), \(k,l \in K\), \(i \ne j\), be binary variables to characterize the mutual position of item parts (i, k) and \((j,l)\) in the pattern of the bar relaxation. To guarantee that the item parts can be packed into the strip, using an minimal height H, we add the following constraint:

$$\begin{aligned} y_{ik} + h_{ik} \le y_{i,k+1}, \quad&i \in I, \quad k=1 , \ldots , s-1, \end{aligned}$$
(15)
$$\begin{aligned} y_{is} + h_{is} \le H, \quad&i \in I, \end{aligned}$$
(16)
$$\begin{aligned} 0 \le x_{ik} \le 1-w_i, \quad&i \in I, \quad k \in K, \end{aligned}$$
(17)
$$\begin{aligned} x_{ik} + w_i \le x_{jl} +1-u_{ikjl}, \quad&i , j \in I, \quad k , l \in K, \quad i \ne j, \end{aligned}$$
(18)
$$\begin{aligned} y_{ik} + h_{ik} \le y_{jl} +1-v_{ikjl}, \quad&i,j \in I, \quad k,l \in K, \quad (i,k) \ne (j,l), \end{aligned}$$
(19)
$$\begin{aligned} u_{ikjl}+u_{jlik}+v_{ikjl}+v_{jlik}=1, \quad&i , j \in I, \quad k , l \in K, \quad i \ne j. \end{aligned}$$
(20)

Summarizing, the whole model to compute an instance with maximal worst-case performance ratio is as follows:

$$H \rightarrow \min $$

subject to constraints

  1. 1.

    (6)–(7) for the size parameters of the items,

  2. 2.

    (8)–(12) for the feasibility of the instance computed,

  3. 3.

    (13)–(20) for the partition of items and feasible packability of all item parts,

  4. 4.

    (1)–(5) for the optimality of the (current) pattern and optimal height 1.

To extend the model to the horizontal contiguous bar relaxation, we just need to replace constraints (15) by

$$\begin{aligned} y_{ik} + h_{ik} = y_{i,k+1}, \quad i \in I, \quad k=1 , \ldots , s-1,\qquad {(15*)} \end{aligned}$$

which ensure that the solution of the relaxation fulfills the contiguous property.

3 Preliminary Results

Up to now, we have only solved the model with a given small number N of items which are partitioned each into \(s=2\) item parts. For the horizontal bar relaxation we observed, that the patterns of the solutions have the same structure, which is displayed in Fig. 2 for the case \(N=4\).

Fig. 2
figure 2

Instance with maximal worst-case performance ratio for \(N=4\) and \(s=2\)

Full size image

The height of the solution of the bar relaxation is always equal to \(N/(2N-2)\) which asymptotically proves that the absolute worst case performance ratio of the horizontal bar relaxation is at least 2.

We also applied the model for the contiguous horizontal bar relaxation for only small N and s. But up to now all solutions obtained provide lower bound 1, and therefore, ratio 1. For larger n, we will get absolute worst-case performance ratios larger than 1, due to [1]

4 Conclusions and Outlook

In this paper, we proposed a new approach to obtain worst-case instances for the two-dimensional Strip Packing Problem when the number of items and item parts is limited. We implemented this approach for two lower bounds and presented first promising results for the horizontal bar relaxation. We are optimistic that we will obtain similar results for the contiguous horizontal bar relaxation.

It will be part of our future work to apply this approach to other lower bounds. Moreover, we will try to improve the model by further examining the structure of the problem and optimizing the performance of our approach with respect to this structure.