Polynomial and Pseudopolynomial Algorithms for Two Classes of Bin Packing Instances
This solves a long-standing open problem in combinatorial optimization for manufacturing and logistics, providing efficient algorithms for previously intractable instances.
The paper tackles the challenging AI and ANI classes of bin packing instances, which had remained unsolved by state-of-the-art methods, by showing they are not strongly NP-hard and presenting polynomial and pseudopolynomial algorithms that solve all benchmark instances orders of magnitude faster than previous approaches.
Cutting and packing problems are fundamental in manufacturing and logistics, as they aim to minimize waste and improve efficiency. The Cutting Stock Problem (CSP) concerns material cutting, whereas the Bin Packing Problem (BPP) concerns packing items into bins. Since the 1960s, these problems have been widely studied because of their industrial relevance and computational complexity. Over time, exact algorithms, often based on mixed-integer programming (MIP), have become able to solve increasingly large instances, often with hundreds of items, within minutes. In 2016, Delorme et al. showed that the algorithm BELOV, combined with a modern version of CPLEX, could solve all benchmark instances available at that time within ten minutes. Motivated by this progress, they introduced two new classes of instances, AI and ANI, which proved extremely challenging for all exact solvers and have guided research on CSP and BPP over the past decade. Despite significant subsequent advances, 13 out of 500 of these instances remain unsolved by state-of-the-art algorithms within a one-hour time limit. In this paper, we show that although AI and ANI instances are particularly hard for MIP-based methods, the BPP restricted to these classes is not strongly NP-hard. We present polynomial-time algorithms for the AI class and pseudopolynomial-time algorithms for the ANI class. Our best algorithms solve all benchmark instances from these classes orders of magnitude faster than previous approaches. They are also straightforward to adapt to the Skiving Stock Problem (SSP), which can be seen as a counterpart of the CSP. Additionally, they can be used as preprocessing routines in exact methods, as their runtime is independent of the instance class, although they are guaranteed to return an optimality status only for instances belonging to the class for which they were designed.