PrecPack: An Efficient Open-Source Exact Solver for Bin Packing with Generalized Precedence Constraints
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.
Related
- A proof of the generalized packing-covering conjecture
- Auxiliary Codes and the Generalized Packing-Covering Conjecture
- On the Generalized Packing and Covering Radii of Codes
- Eventual convexity for separable chance constraints with skewed generalized hyperbolic random variables
- Efficient computation of mixture confidence sequences in generalized linear models
BibTeX
@misc{wang2026precpack,
title = {{PrecPack: An Efficient Open-Source Exact Solver for Bin Packing with Generalized Precedence Constraints}},
author = {Sunkanghong Wang and Zhengzhong Ricky You and Roberto Baldacci and Baichuan Mo and Hu Qin and Lijun Wei and Zhou Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17368},
eprint = {2609.17368},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17368},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - PrecPack: An Efficient Open-Source Exact Solver for Bin Packing with Generalized Precedence Constraints
AU - Sunkanghong Wang
AU - Zhengzhong Ricky You
AU - Roberto Baldacci
AU - Baichuan Mo
AU - Hu Qin
AU - Lijun Wei
AU - Zhou Xu
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17368
UR - https://arxiv.org/abs/2609.17368
AB - 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.
ER -