Bin packing with many items solved efficiently by new algorithm
High-Multiplicity Bin Packing is FPT
Data Structures and Algorithms
Summary
Bin packing is a puzzle where you try to fit items of different sizes into limited bins. This paper deals with a tough version where there are many items but only a few distinct sizes. Previous solutions were slow when the number of sizes grew. The authors found a new way to solve this quickly by turning the problem into a special math equation and cleverly grouping item arrangements. This approach guarantees a correct packing in a reasonable time when the number of sizes is small.
What this means in practice
- •For logistics planners: Improve allocation of large groups of similarly sized packages into containers when the variety of package sizes is limited.
- •For manufacturing schedulers: Optimize grouping of parts with few size variants into production batches efficiently when handling many items.
A theory result. No direct application yet.
Authors
Tomohiro Koana, Soh Kumabe
Abstract
Bin packing asks whether a collection of items can be packed into at most a given number of bins of a given capacity. We consider the high-multiplicity setting with $d$ distinct item sizes, in which both the item sizes and the number of items of each size are encoded in binary. Goemans and Rothvos (JACM 2020) gave an XP algorithm parameterized by $d$. Whether this problem is fixed-parameter tractable (FPT) in $d$ has remained a central open problem. We resolve this question by giving a deterministic $O^*(2^{d^{O(d)}})$-time algorithm. We formulate bin packing as an integer linear program (ILP) with at most $(d+1)d^d$ variables. A bin configuration records the number of items of each type in one bin. We partition these configurations by their coordinate remainders modulo $d$. For each class, we use one variable for the bin count and $d$ variables for the total item counts. The convex hull of each class has the integer decomposition property, which guarantees that every feasible ILP solution corresponds to a packing.