Source-linked AI summary
High-Multiplicity Bin Packing is FPT
Tomohiro Koana, Soh Kumabe
TL;DR
High-multiplicity bin packing with binary-encoded sizes and multiplicities had remained an open question for fixed-parameter tractability in the number of item types. This paper formulates the problem as an ILP using grouped bin configurations and proves a deterministic FPT running time of O*(2^{d^{O(d)}}).
Problem
Whether high-multiplicity bin packing with binary-encoded sizes and multiplicities is FPT in the number d of item types remained open.
Source: §1 · p. 1Method
The algorithm formulates bin packing as an ILP using bin configurations grouped by coordinate remainders modulo d.
Source: §2 · p. 3Results
O*(2^{d^{O(d)}}) time suffices to decide Bin Packing deterministically.
Source: §1 · p. 2Takeaways & Limitations
Bin Packing is fixed-parameter tractable in d even when item sizes and multiplicities are encoded in binary.
Source: §1 · p. 2
Abstract
from arXiv · showhide
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.
1 Introduction
For high-multiplicity bin packing with binary-encoded item sizes and multiplicities, whether the problem is FPT in the number of item types remained open. The paper resolves this question with a deterministic FPT algorithm based on an ILP formulation.
1 Introduction
- Earlier additive-one approximation and convex-hull-vertex algorithms did not establish FPT in d alone.The former permits one extra bin, while the latter depends on a vertex-set size not bounded by a function of d alone.Source: §1 · p. 2
- The open question concerned binary-encoded sizes and multiplicities, after earlier results gave XP but not FPT in d alone.For unary encoding of either sizes or multiplicities, FPT algorithms in d were known; the simultaneous binary case remained open.Source: §1 · pp. 1–2
- Under ETH, a lower bound for high-multiplicity bin packing requires any FPT running time f(d)L^O(1) to have f(d)=2^{2^{Ω(d)}}.The cited work rules out running time L^{2^{o(d)}}.Source: §1 · p. 2
- O*(2^{d^{O(d)}}) time suffices to decide high-multiplicity Bin Packing deterministically.The algorithm is fixed-parameter tractable in the number d of item types.Source: §1 · p. 2
- The ILP groups bin configurations by coordinate remainders modulo d and uses bin-count and item-total variables for each group.A bin configuration records the number of items of each type in one bin; the integer decomposition property ensures feasible integral totals correspond to feasible configurations.Source: §1 · p. 2
2 An integer linear programming formulation
The formulation groups bin configurations by coordinate remainders modulo d, then uses the integer decomposition property to show that integral ILP solutions correspond exactly to packings.
2 An integer linear programming formulation
- The ILP uses D = (d + 1)d^d variables, grouping bins by coordinatewise remainders modulo d and recording each group’s bin count and configuration sum.For each residue vector r, the variables n_r and z_r represent those quantities.Source: §2 · p. 3
- Each P_r is the convex hull of configurations in one residue class, and every integer point of P_r is still a feasible bin configuration.Source: §2 · p. 3
- Count constraints enforce the total bin count b and item counts a, while each pair (z_r, n_r) must belong to its residue class cone C_r.The ILP asks whether the resulting polytope K contains an integer point.Source: §2 · p. 3
- The integer decomposition property of each P_r lets any integral cone pair yield n_r feasible bin configurations summing to z_r, establishing the converse from ILP feasibility to packing.Source: §2 · p. 4
- The ILP is equivalent to bin packing, but its cone constraints require a strong separation oracle because an explicit inequality description is unavailable.Source: §2 · p. 5
3 Separation and the algorithm
The algorithm decides bin packing by searching for an integer point in a bounded convex set using strong separation oracles. It builds separation over the configuration-class polytopes and combines those oracles for the full set, yielding a deterministic O*(2^{d^{O(d)}})-time algorithm.
3 Separation and the algorithm
- The bounded-convex-set search finds a point in Q ∩ Z^n or certifies it is empty using at most 2^{O(n^3)}σ^{O(1)} separation calls.Its hypotheses require Q ⊆ [−T,T]^n and separation inequalities of encoding length (σ + ℓ)^{O(1)}.Source: §3 · p. 5
- The search is applied to K with n = D and σ = D + L + enc(T), where T = 1 + max{b, a1, …, ad}.The count constraints bound K within [−T,T]^D, and the oracle for K has output length (D + L + ℓ)^{O(1)}.Source: §3 · p. 5
- 2^{O(d^3)}(L + ℓ)^{O(1)} bit operations suffice for strong separation over each P_r, with output length (d + L + ℓ)^{O(1)}.Optimization over P_r is implemented by a d-variable integer program; after clearing denominators, Lenstra’s algorithm returns an optimal integer vector.Source: §3 · p. 5
- Lemma 8 establishes that strong separation over K takes 2^{O(d^3)}(L + ℓ)^{O(1)} bit operations, with returned inequality length (D + L + ℓ)^{O(1)}.Source: §3 · p. 6
- O*(2^{d^{O(d)}}) time suffices to decide Bin Packing deterministically.The algorithm reduces the problem to finding an integer point in K, then applies bounded-convex-set lattice search using the strong separation oracle.Source: §3 · p. 6
Declaration of generative AI use
The authors state that ChatGPT 6 Astra generated the proof of Theorem 1 and was used to draft the manuscript; the authors verified and revised both and take full responsibility.
Declaration of generative AI use
- ChatGPT 6 Astra generated the proof of Theorem 1 and helped draft the manuscript; the authors verified and revised both and take full responsibility.The declaration concerns the proof and manuscript.Source: Declaration of generative AI use · p. 6