PrecPack solver improves packing with precedence and capacity limits
PrecPack: An Efficient Open-Source Exact Solver for Bin Packing with Generalized Precedence Constraints
Data Structures and Algorithms
Summary
Packing items into bins becomes tricky when some items must be packed before others and bins have limited space. The authors present PrecPack, a computer program that finds the best way to pack items while respecting these order and size rules. Their program is open-source, faster, and more accurate than previous methods on standard test problems. It uses a clever approach to remember and avoid repeating calculations and ensures trustworthy results without needing commercial software.
What this means in practice
- •For manufacturing planners: Optimize packing and assembly schedules that must respect item order and bin capacity to reduce resource use and costs.
- •For logistics software developers: Integrate PrecPack to improve exact solutions for shipment loading problems with complex item dependencies and container limits.
Authors
Sunkanghong Wang, Zhengzhong Ricky You, Roberto Baldacci, Baichuan Mo, Hu Qin, Lijun Wei, Zhou Xu
Abstract
Efficient resource use in packing and assembly-line applications requires decisions that jointly account for capacity and precedence constraints. The strongly NP-hard bin packing problem with generalized precedence constraints (BPP-GP) models such decisions by minimizing the number of ordered, capacitated bins required to pack weighted items, even when precedence requirements span multiple bins. Existing exact algorithms primarily focus on classical special cases, whereas general BPP-GP has been addressed only via compact integer models and heuristics, with no efficient open-source exact solver. We present PrecPack, a unified exact solver that extends branch-bound-and-remember (BBR) to arbitrary nonnegative precedence weights and naturally specializes to the classical cases. Generalized states capture restrictions that remain active across future bins, which are addressed through branching, dominance, and conflict-aware lower bounds. Root column generation uses fixed-point arithmetic to compute numerically valid dual bounds for pruning or to prove optimality. To support reuse and verification, we provide common programming and command-line interfaces, independent assignment checking, explicit termination statuses, and reproducible batch execution; the core procedures require no commercial software. In same-machine, single-threaded comparisons on classic assembly-line benchmarks, more instances are proven optimal, and average computing times are substantially reduced relative to leading source-available BBR implementations. Further comparisons with published benchmark results for bin packing with precedence constraints and BPP-GP also show that more instances were proved optimal and that reported average gaps were smaller on most benchmark sets. PrecPack is released under the MIT License at https://github.com/Sunkanghong-Wang/PrecPack.