Polynomial and Pseudopolynomial Algorithms for Two Classes of Bin Packing Instances
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915919348891648 |
|---|---|
| author | da Silva, Renan Fernando Franco de Lima, Vinícius Loti Schouery, Rafael C. S. Côté, Jean-François Iori, Manuel |
| author_facet | da Silva, Renan Fernando Franco de Lima, Vinícius Loti Schouery, Rafael C. S. Côté, Jean-François Iori, Manuel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05152 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Polynomial and Pseudopolynomial Algorithms for Two Classes of Bin Packing Instances da Silva, Renan Fernando Franco de Lima, Vinícius Loti Schouery, Rafael C. S. Côté, Jean-François Iori, Manuel Data Structures and Algorithms 90C27, 90C57, 90C39 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. |
| title | Polynomial and Pseudopolynomial Algorithms for Two Classes of Bin Packing Instances |
| topic | Data Structures and Algorithms 90C27, 90C57, 90C39 |
| url | https://arxiv.org/abs/2604.05152 |