A regular perspective on solving the irregular strip packing problem with the dotted-board model: a mosaic approach and a divide-and-conquer strategy

Since its introduction in 2013, the dotted-board model has been widely used by the cutting and packing research community to tackle irregular packing problems. However, despite its popularity, little research has aimed at improving its performance when solved via off-the-shelf integer programming solvers, beyond the known strategy of merging pairwise incompatibility constraints into clique constraints during a somewhat lengthy preprocessing. In this work, we bridge this gap by introducing two complementary contributions that bring regular packing concepts to the irregular strip packing problem. In particular, we propose a mosaic approach in which each fragment corresponds to a physical location on the strip and is associated with a clique constraint in the dotted-board model. We also present a divide-and-conquer strategy in which fragments are first computed over a single 1×1 tile of the strip and subsequently extended to the entire strip. Furthermore, we evaluate techniques to reduce the number of constraints and non-zero coefficients in the resulting models, along with alternative formulations for the objective function. Our contributions result in a competitive approach capable of solving benchmark instances previously unsolved in the literature. But more importantly, they offer new perspectives on the dotted-board model, highlighting its structural resemblance to models in regular packing, which, alongside our open-source implementation, will hopefully encourage further research on the topic.

Article

Download

View PDF