pith. sign in

arxiv: 2604.05152 · v1 · submitted 2026-04-06 · 💻 cs.DS

Polynomial and Pseudopolynomial Algorithms for Two Classes of Bin Packing Instances

Renan Fernando Franco da Silva , Vin\'icius Loti de Lima , Rafael C. S. Schouery , Jean-Fran\c{c}ois C\^ot\'e , Manuel Iori This is my paper

Pith reviewed 2026-05-10 18:47 UTC · model grok-4.3

classification 💻 cs.DS
keywords bin packingAI instancesANI instancespolynomial algorithmspseudopolynomial algorithmscutting stockskiving stock
0
0 comments X

The pith

Bin packing on AI and ANI classes admits polynomial and pseudopolynomial algorithms

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Although the AI and ANI instance classes were introduced precisely because they defeat state-of-the-art MIP solvers, the bin packing problem restricted to these classes is not strongly NP-hard. The paper gives polynomial-time algorithms that solve every AI instance and pseudopolynomial-time algorithms that solve every ANI instance. These procedures solve all benchmark instances from the two classes orders of magnitude faster than prior exact methods, can be used as preprocessing routines for general solvers, and adapt directly to the skiving stock problem.

Core claim

The bin packing problem restricted to the AI class admits a polynomial-time algorithm while the same problem restricted to the ANI class admits a pseudopolynomial-time algorithm; consequently these two families, despite being hard for mixed-integer programming, are not strongly NP-hard.

What carries the argument

Specialized exact algorithms that exploit the structural properties defining the AI and ANI classes to achieve polynomial or pseudopolynomial running times.

Load-bearing premise

The benchmark instances truly belong to the AI or ANI classes as defined and the proposed algorithms correctly identify and exploit the structural properties of these classes to achieve the claimed time bounds.

What would settle it

An instance certified to be in the AI class on which the polynomial algorithm either returns a suboptimal packing or fails to terminate in polynomial time (or the analogous failure for an ANI instance under the pseudopolynomial algorithm).

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper claims that the Bin Packing Problem restricted to the AI class of instances (as defined by Delorme et al.) admits a polynomial-time algorithm, while the ANI class admits a pseudopolynomial-time algorithm. These algorithms are asserted to solve all 500 benchmark instances orders of magnitude faster than prior MIP-based exact methods, to be adaptable to the Skiving Stock Problem, and to serve as preprocessing routines whose runtime is independent of instance class (though optimality is guaranteed only on the target class).

Significance. If the algorithms correctly exploit the structural properties of the AI and ANI classes for arbitrary instances and the complexity bounds hold in general, the result would be significant: it would establish that these long-standing benchmark classes are not strongly NP-hard, supply practical exact solvers for instances that have resisted MIP approaches, and offer reusable preprocessing components for general BPP solvers.

major comments (3)
  1. [§3] §3 (AI algorithm): The polynomial-time claim rests on the algorithm enumerating a polynomially bounded set of feasible bin patterns derived from the AI class definition. The manuscript does not explicitly prove that the AI structural property (item sizes being integer multiples of a common divisor or similar) guarantees a polynomial bound on the number of patterns for every possible AI instance, rather than only those whose numeric parameters match the benchmark distribution.
  2. [§4] §4 (ANI algorithm): The pseudopolynomial bound is stated to be O(n * W^2) or similar, where W is the bin capacity. It is unclear whether the dynamic-programming recurrence correctly handles arbitrary multiplicities and item sizes within the ANI class definition without additional assumptions on the range of item sizes that may not hold for all members of the class.
  3. [§6] §6 (experimental evaluation): The reported speedups are demonstrated only on the 500 fixed benchmarks. No additional experiments or worst-case analysis on larger synthetic AI/ANI instances (with n >> 100 or item sizes drawn from the full class definition) are provided to confirm that the observed runtimes scale according to the claimed polynomial/pseudopolynomial bounds rather than benefiting from benchmark-specific structure.
minor comments (2)
  1. [§2] The definition of the AI and ANI classes in §2 should include a self-contained formal statement rather than relying solely on the citation to Delorme et al., to allow readers to verify the structural properties used by the algorithms.
  2. [§6] Figure 1 (or the corresponding runtime plot) would benefit from log-scale y-axis and explicit comparison against the best prior exact solver on the same machine to make the 'orders of magnitude' claim easier to assess.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their thorough review and valuable comments on our paper. We address each of the major comments below and outline the revisions we will make to the manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (AI algorithm): The polynomial-time claim rests on the algorithm enumerating a polynomially bounded set of feasible bin patterns derived from the AI class definition. The manuscript does not explicitly prove that the AI structural property (item sizes being integer multiples of a common divisor or similar) guarantees a polynomial bound on the number of patterns for every possible AI instance, rather than only those whose numeric parameters match the benchmark distribution.

    Authors: Thank you for highlighting this. The manuscript's Section 3 provides a proof that the common divisor property in the AI class definition allows enumeration of all feasible patterns in time polynomial in n, as the scaled instance has item sizes that permit a combinatorial bound independent of the original W. This applies to any instance in the class, not just benchmarks. To make this clearer, we will add an explicit statement and proof sketch in the revised version. revision: yes

  2. Referee: [§4] §4 (ANI algorithm): The pseudopolynomial bound is stated to be O(n * W^2) or similar, where W is the bin capacity. It is unclear whether the dynamic-programming recurrence correctly handles arbitrary multiplicities and item sizes within the ANI class definition without additional assumptions on the range of item sizes that may not hold for all members of the class.

    Authors: We thank the referee for this comment. The DP recurrence in Section 4 is formulated to handle arbitrary multiplicities by using a multi-dimensional state or by processing items one type at a time, with the time complexity O(n W^2) arising from the fill level and previous states. The ANI class definition does not impose extra range assumptions beyond what is needed for the pseudopolynomial bound. We will revise the section to include a more detailed explanation of how the recurrence works for general multiplicities within the class. revision: yes

  3. Referee: [§6] §6 (experimental evaluation): The reported speedups are demonstrated only on the 500 fixed benchmarks. No additional experiments or worst-case analysis on larger synthetic AI/ANI instances (with n >> 100 or item sizes drawn from the full class definition) are provided to confirm that the observed runtimes scale according to the claimed polynomial/pseudopolynomial bounds rather than benefiting from benchmark-specific structure.

    Authors: The experiments in Section 6 are performed on the standard benchmark set to show practical superiority. However, we agree that to fully support the complexity claims, additional tests on larger instances are desirable. We will add results from synthetic AI and ANI instances with increased n and W to demonstrate the scaling behavior in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithms are independent constructions for externally defined classes

full rationale

The paper defines polynomial-time algorithms for the AI class and pseudopolynomial-time algorithms for the ANI class of BPP instances, where the classes themselves originate from prior independent work by Delorme et al. The derivation proceeds by exhibiting explicit algorithms that exploit the structural properties stated in the class definitions, with time-complexity analysis following directly from those properties rather than from any fitted parameters, self-referential definitions, or load-bearing self-citations. No step renames a known result, imports a uniqueness theorem from the same authors, or presents a prediction that reduces to an input by construction. The claim that the restricted problems are not strongly NP-hard is therefore a direct consequence of the exhibited algorithms and is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the prior definition of the AI and ANI instance classes and on standard notions of polynomial and pseudopolynomial time from computational complexity theory.

axioms (1)
  • domain assumption Bin packing instances belonging to the AI and ANI classes possess exploitable structural properties that permit polynomial or pseudopolynomial exact solution.
    This is the key premise that allows the algorithms to run in the stated time bounds.

pith-pipeline@v0.9.0 · 5660 in / 1259 out tokens · 63260 ms · 2026-05-10T18:47:51.686424+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    INFORMS Journal on Computing 36(1):141--162, doi: 10.1287/ijoc.2022.0257

    A numerically exact algorithm for the bin- packing problem. INFORMS Journal on Computing 36, 141–162. doi:10.1287/ijoc.2022.0257. Belov, G., Scheithauer, G.,

    work page doi:10.1287/ijoc.2022.0257 2022

  2. [2]

    European Journal of Operational Research 171, 85–106

    A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. European Journal of Operational Research 171, 85–106. doi:10.1016/j.ejor.2004.08.036. 24 Caprara, A., Dell’Amico, M., Díaz-Díaz, J.C., Iori, M., Rizzi, R.,

    work page doi:10.1016/j.ejor.2004.08.036 2004

  3. [3]

    Annals of Operations Research 86, 629–659

    Exactsolutionofbin-packingproblemsusingcolumngenerationand branch-and-bound. Annals of Operations Research 86, 629–659. doi:10.1023/A:1018952112615. Coffman, E.G., Garey, M.R., Johnson, D.S.,

    work page doi:10.1023/a:1018952112615

  4. [4]

    Springer Vienna

    Approximation Algorithms for Bin-Packing — An Updated Survey. Springer Vienna. pp. 49–106. doi:10.1007/978-3-7091-4338-4_3. CoffmanJr., E.G., Csirik, J., Galambos, G., Martello, S., Vigo, D.,

    work page doi:10.1007/978-3-7091-4338-4_3

  5. [5]

    INFORMS Journal on Computing 32, 101–119

    Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS Journal on Computing 32, 101–119. doi:10.1287/ijoc.2018.0880. Delorme, M., Iori, M., Martello, S.,

    work page doi:10.1287/ijoc.2018.0880 2018

  6. [6]

    European Journal of Operational Research 255, 1–20

    Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research 255, 1–20. doi:10.1016/ j.ejor.2016.04.030. Dyckhoff, H.,

    work page 2016

  7. [7]

    European Journal of Operational Research 44, 145–159

    A typology of cutting and packing problems. European Journal of Operational Research 44, 145–159. doi:10.1016/0377-2217(90)90350-K. Garey, M.R., Johnson, D.S.,

    work page doi:10.1016/0377-2217(90)90350-k

  8. [8]

    Springer Vienna, Vienna

    Approximation Algorithms for Bin Packing Problems: A Survey. Springer Vienna, Vienna. pp. 147–172. doi:10.1007/978-3-7091-2748-3_8. Gilmore, P.C., Gomory, R.E.,

    work page doi:10.1007/978-3-7091-2748-3_8

  9. [9]

    Operations Research 9, 849–859

    A linear programming approach to the cutting-stock problem. Operations Research 9, 849–859. doi:10.1287/opre.9.6.849. Heßler, K., Irnich, S., Kreiter, T., Pferschy, U.,

    work page doi:10.1287/opre.9.6.849

  10. [10]

    OR Spectrum 44, 1–43

    Bin packing with lexicographic objectives for loading weight- and volume-constrained trucks in a direct-shipping system. OR Spectrum 44, 1–43. doi:10.1007/s00291-021-00628-x. Kantorovich, L.V.,

    work page doi:10.1007/s00291-021-00628-x

  11. [11]

    Mathematical Programming 197, 813–846

    Exact solution of network flow models with strong relaxations. Mathematical Programming 197, 813–846. doi:10.1007/s10107-022-01785-9. Martello, S., Toth, P.,

    work page doi:10.1007/s10107-022-01785-9

  12. [12]

    International Journal of Production Research 61, 2895–2916

    Models for two- and three-stage two- dimensional cutting stock problems with a limited number of open stacks. International Journal of Production Research 61, 2895–2916. doi:10.1080/00207543.2022.2070882. Martinovic, J., Scheithauer, G.,

    work page doi:10.1080/00207543.2022.2070882 2022

  13. [13]

    European Journal of Operational Research 251, 356–368

    Integer linear programming models for the skiving stock problem. European Journal of Operational Research 251, 356–368. doi:10.1016/j.ejor.2015. 11.005. 25 Pessoa, A., Sadykov, R., Uchoa, E., Vanderbeck, F.,

    work page doi:10.1016/j.ejor.2015 2015

  14. [14]

    INFORMS Journal on Computing doi:10.1287/ ijoc.2023.0399

    Solving cutting stock problems via an extended ryan-foster branching scheme and fast column generation. INFORMS Journal on Computing doi:10.1287/ ijoc.2023.0399. Uchoa, E., Sadykov, R.,

    work page arXiv 2023

  15. [15]

    Technical Report L-2024-1

    Kantorovich and Zalgaller (1951): The 0-th Column Generation Algorithm. Technical Report L-2024-1. Cadernos do LOGIS-UFF. Niterói, Brazil. Vance, P.H.,

    work page 1951

  16. [16]

    Computational Optimization and Applications 9, 211–228

    Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optimization and Applications 9, 211–228. doi:10.1023/A:1018346107246. Vance, P.H., Barnhart, C., Johnson, E.L., Nemhauser, G.L.,

    work page doi:10.1023/a:1018346107246

  17. [17]

    Computational Optimization and Appli- cations 3, 111–130

    Solving binary cutting stock problems by column generation and branch-and-bound. Computational Optimization and Appli- cations 3, 111–130. doi:10.1007/BF01300970. Wei, L., Luo, Z., Baldacci, R., Lim, A.,

    work page doi:10.1007/bf01300970

  18. [18]

    INFORMS Journal on Computing 32, 428–443

    A new branch-and-price-and-cut algorithm for one- dimensional bin-packing problems. INFORMS Journal on Computing 32, 428–443. doi:10.1287/ ijoc.2018.0867. Wäscher, G., Haußner, H., Schumann, H.,

    work page arXiv 2018

  19. [19]

    European Jour- nal of Operational Research181(1), 59–75 (2007)

    An improved typology of cutting and packing problems. European Journal of Operational Research 183, 1109–1130. doi:10.1016/j.ejor. 2005.12.047. 26

    work page doi:10.1016/j.ejor 2005