Decoupling Geometry from Optimization in 2D Irregular Cutting and Packing Problems: An Open-Source Collision Detection Engine

Addressing irregular cutting and packing (C&P) optimization problems poses two distinct challenges: the geometric challenge of determining whether an item can be feasibly placed at a certain position and the optimization challenge of finding a good solution according to some objective function. Until now, those tackling such problems have had to address both challenges simultaneously, requiring two distinct sets of expertise and a lot of research and development effort. One way to lower this barrier is to decouple the two challenges. In this paper, we introduce a powerful collision detection engine (CDE) for two-dimensional (2D) irregular C&P problems, which assumes full responsibility for the geometric challenge. The CDE (i) allows users to focus with full confidence on their optimization challenge by abstracting geometry away, and (ii) enables independent advances to propagate to all optimization algorithms built atop it. We present a set of core principles and design philosophies to model a general and adaptable CDE focused on maximizing performance, accuracy, and robustness. These principles are accompanied by a concrete open-source implementation called jagua-rs. This paper, together with its implementation, serves as a catalyst for future advances in irregular C&P problems by providing a solid foundation that can either be used as it currently exists or further improved upon.

History: Accepted by Ted Ralphs, Area Editor for Software Tools.

Funding: This work was supported by Research Foundation – Flanders (FWO) [Grants 1S71222N and K804824N].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1025) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.1025). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.