(132d) A New MILP Model for the 2-D Strip Packing Problem

The two-dimensional strip packing problem has many applications in the steel, textile and paper industries. It consists of orthogonally packing a set of rectangles into one rectangular container, the strip, with a fixed width and variable height so as to minimize the height of the strip (Kenmochi et al., EJOR 2009, 73-83).

Strip packing problems are closely related to scheduling problems which can be viewed as being one dimensional. In scheduling, a variety of time representations can be used to solve the problem such as discrete-time and continuous-time, the latter relying on sequencing variables or time grid based approaches, using either single or multiple time grids. The obvious starting point for strip packing is a 2-D discrete-space approach, where under the assumption of integer data, one uses 1x1 squares to generate the matrix. To determine the optimal strip height one can start with the continuous lower bound (Kenmochi et al., 2009) and apply the algorithm proposed by Maravelias & Grossmann (2003) for makespan minimization, which works in the infeasible region until finding the optimal solution (first feasible solution).

In this paper, we propose an alternative mixed discrete/continuous-space approach, discrete on the x-domain and continuous in the y-domain. The aim is to define the strip height as an explicit continuous variable and hence remove the iterative search procedure. We rely on excess resource variables and constraints, from the Resource-Task Network, to ensure that there is no overlap between rectangles. Furthermore, we use the concept of event points and use variables to determine the y-coordinate of event point y in time grid x. Note that multiple space grids are used for the x-domain, one for each element. Interestingly, a search procedure is replaced by another since it is widely known that the optimal solution is dependent on the specified number of event points.

The performance of the discrete and mixed approaches is compared through the solution of 29 test cases taken from the literature. While the performance is similar, the new approach has the advantage of always leading to very good solutions while for the discrete-space algorithm one gets the optimal solution or none at all.

The approach is also compared to two other from the PSE community, which can be classified as being continuous-time using variables related to the (x,y) coordinates of the rectangles on the strip. Sawaya and Grossmann (2005) proposed a GDP model that was reformulated into a MILP using either a convex hull of big-M approach, which is shown to have a large integrality gap and worse computational performance despite the use of 62 cuts. The approach by Westerlund et al. (2007), using big-M and symmetry breaking constraints features the same relaxation and similar performance when taking into account the differences in computational hardware and software.

Finally, we also compare to 5 highly specialized algorithms from the OR community, which not surprisingly tend to be more efficient overall. However, it is interesting to find out that the discrete-space approach is rapidly catching up in the perfect packing problems for which the excess resource variables can be made equal to 0, which tends to make RTN-based model more efficient.