Mixed-integer linear programming models for 3D irregular strip packing problems

Exact solution methods for two-dimensional irregular strip-packing problems have been studied and refined over the years. In contrast, the three-dimensional version of the problem has only been addressed through heuristic solution methods or approximating representations, resulting in a lack of optimal solutions. This paper addresses this gap in the literature by formulating and solving exact models of three-dimensional irregular strip packing problems. When taking these foundational first steps, we will focus on instances with convex items and not consider rotation of the items. The most challenging aspect when modelling such problems is the formulation of separation constraints that ensure that none of the items overlap. Many of the exact models introduced for two-dimensional problems tackle this challenge using No-Fit Polygons, which describe the relative placements for which two items overlap. For our three-dimensional case, we introduce a mixed integer linear programming formulation based on their conceptual equivalents: No-Fit Polyhedra. A basic first model can be formulated in a relatively straightforward manner, but it exhibits weak linear relaxations and a high degree of symmetry. Therefore, we investigate whether the techniques used to strengthen two-dimensional formulations can also be adapted for our three-dimensional context. An extensive set of instances is introduced to thoroughly benchmark the impact of these techniques and to evaluate their overall performance.