PaperlayerView exact revision on arXiv

Source-linked AI summary

PrecPack: An Efficient Open-Source Exact Solver for Bin Packing with Generalized Precedence Constraints

Sunkanghong Wang, Zhengzhong Ricky You, Roberto Baldacci, Baichuan Mo, Hu Qin, Lijun Wei, Zhou Xu

arXiv:2609.17368v1cs.DSmath.COmath.OC

TL;DR

Generalized precedence constraints make bin packing difficult, especially when requirements span ordered bins. PrecPack extends branch-bound-and-remember into a unified exact solver for arbitrary precedence weights. It proved 523 of 525 SALBP-I instances optimal, versus 456 or 457 for each of three source-available BBR implementations, and outperformed published results on broader benchmarks.

  • Problem

    BPP-GP is strongly NP-hard and imposes generalized precedence constraints across ordered bins, complicating capacity-constrained packing decisions.

  • Method

    PrecPack extends branch-bound-and-remember to arbitrary nonnegative precedence weights for unified exact solution of generalized precedence-constrained bin packing.

  • Results

    523 of 525 SALBP-I instances were proved optimal, compared with 456 or 457 for each of three source-available BBR implementations.

  • Takeaways & Limitations

    Across published BPP-P and BPP-GP benchmarks, PrecPack proved more instances optimal and reported smaller average gaps on most matched benchmark sets.

  • Takeaways & Limitations

    General-purpose integer-programming formulations are generally limited to proving optimality for very small instances.

Abstract

from arXiv · show

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.

1. Introduction

BPP-GP jointly models capacitated packing and precedence requirements that can remain active across multiple ordered bins, making existing compact formulations difficult to scale. PrecPack addresses this gap with a unified open-source exact solver that handles arbitrary nonnegative precedence weights and naturally specializes to SALBP-I and BPP-P.

  • Problem: BPP-GP couples capacity and precedence decisions because precedence weights can make successors ineligible for the same or several subsequent bins.Positive weights can require intermediate empty bins, so minimizing the last-bin index differs from minimizing the number of nonempty bins.
  • Motivation: A compact integer formulation is generally limited to proving optimality for very small BPP-GP instances, motivating dedicated exact algorithms.The formulation represents ordered bins and accounts for intermediate empty bins required by positive precedence weights.
  • Contribution: PrecPack provides the first BBR-based exact method for BPP-GP with arbitrary nonnegative precedence weights and a last-bin-index objective.The solver unifies the generalized problem with its classical special cases when all precedence weights are zero or one.
  • Results: 1.79 seconds is PrecPack’s average computing time across these instances, versus 50.39 to 55.18 seconds for the three source-available BBR implementations.Further published benchmark comparisons show more instances proved optimal and smaller average gaps on most benchmark sets.

2. The PrecPack Solver

PrecPack combines preprocessing, bound strengthening, heuristic incumbent improvement, and complete BBR search into an exact solver for BPP-GP. Its workflow can prove optimality early, otherwise terminates with validated solutions, bounds, and explicit limit statuses.

  • Initialization and Preprocessing: The solver strengthens bounds before complete search through validation, preprocessing, preliminary heuristics and BBR, a one-fewer-bin test, and direction selection.Preprocessing combines precedence strengthening, conflict-aware capacity tightening, item lifting, direction selection, and topological renumbering; initial bounds combine continuous, precedence-path, window-DFF, and applicable maximum-flow bounds.
  • Termination and Reporting: When LB equals UB, PrecPack proves optimality and skips remaining search; otherwise complete BBR continues until proof or configured time or memory limits.The final step reconstructs original item numbering, independently verifies feasibility, and reports the solution, final bounds, and termination reason.
  • Root-Bound Strengthening: Column generation at the root solves a relaxation whose optimum is a valid lower bound, strengthening LB without explicit bin positions.The relaxation is used to increase LB when it yields a stronger bound, supporting pruning or optimality proofs.
  • Complete BBR Search: Generalized BBR states remember precedence restrictions active across future bins, while dominance and conflict-aware bounds reduce redundant search.The state reduces to the assigned-item set when precedence weights are zero or one, and states with identical feasible future-load sequences can be safely remembered.

3. Software Design, Implementation, and Reproducibility

PrecPack provides a unified C++ implementation through executable and library interfaces, with reusable verification and explicit resource-aware termination. Its portable, reproducible tooling supports independent checking, resumable batch execution, and validation without commercial software.

  • Implementation: PrecPack exposes a common C++ core through standalone executable and library interfaces, allowing users to solve, embed, or extend the solver while reusing instance-handling and verification tools.The public solve API accepts an Instance and Config and returns assignments, bounds, status, and statistics.
  • Implementation: A single BBR implementation serves all three problem classes, with fixed settings selecting applicable rules and simpler representations from precedence weights rather than benchmark names.The Solver API coordinates initialization, optional root strengthening, and the BBR Driver; root strengthening returns a lower bound without maintaining BBR states or determining final termination.
  • Implementation: The implementation controls computational overhead through compact state storage, blocked allocation, hash lookup with full-state collision checks, reusable arrays, and incremental residual-sum updates.Bit masks support eligibility and dominance tests, while precomputed DFF contributions avoid reconstructing successor relations for each branch.
  • Reproducibility: CMake builds the C++20 library and executable on macOS, Linux, and Windows, while preprocessing, heuristics, complete BBR, and validation remain available without optional Gurobi.Fixed orders, tie-breaking rules, and seed 1 determine algorithmic choices, although wall-clock interruption can change completed work.
  • Verification and Reproducibility: Independent assignment checks, exhaustive small-instance references, targeted and randomized bound tests, regression coverage, and cross-platform automated workflows support verification and reproducibility.The repository includes source code and benchmark data, and a separate replication archive preserves the source revision, inputs, settings, raw results, and table-generation scripts.

4. Computational Experiments

PrecPack is evaluated under controlled same-machine conditions against source-available exact solvers and published results across SALBP-I, BPP-P, and BPP-GP. It proves more instances optimal and generally achieves smaller gaps and faster runtimes, with exceptions on the largest SALBP-I groups and one BPP-GP gap comparison.

  • Same-machine comparison: PrecPack proves 523 of 525 SALBP-I instances, exceeding each baseline by 66 or 67 instances, with a 0.008% average gap and 1.79-second average time.The baselines report average gaps of 0.479% to 0.774% and average times of 50.39 to 55.18 seconds.
  • Published SALBP-I comparison: Across published SALBP-I results, PrecPack proves all Scholl instances and smaller Otto groups, exceeds competing proof counts at n = 100 and n ∈{250,500,750}, but trails at n = 1000.At n = 1000, PrecPack proves 306 instances versus 349 or 350 for BBR14 and improved methods under longer limits.
  • Published BPP-P comparison: For BPP-P, PrecPack proves all 20- and 50-item Otto instances, improves proof counts and gaps for larger Otto sizes, but proves 262 of 269 Scholl instances.On Scholl, BB12 proves 266 instances and EA16 proves all 269; at n = 20, PrecPack matches CPLEX’s proof count and gap.

5. Conclusion and Future Research Direction

PrecPack extends BBR to arbitrary nonnegative precedence weights, providing an efficient open-source exact solver for general BPP-GP with reusable and verifiable implementations. It proves stronger benchmark results than source-available and published alternatives, while motivating future extension to two-dimensional cutting stock with precedence constraints.

  • Conclusion: PrecPack generalizes BBR through states retaining outstanding precedence restrictions, empty-bin transitions, generalized dominance rules, and conflict-aware residual bounds.The same procedure specializes naturally to SALBP-I and BPP-P and supports arbitrary nonnegative precedence weights.
  • Conclusion: Published BPP-P and BPP-GP comparisons showed more proven optima and smaller average gaps on most matched benchmark sets.The comparison supports PrecPack’s effectiveness beyond the SALBP-I benchmarks.
  • Future Research Direction: Future work targets two-dimensional cutting stock with precedence constraints for glass production (Parreño and Alvarez-Valdes 2021), adapting exact packing methods and solver mechanisms to geometric feasibility.Wang et al. (2025) provide a starting point for single-bin exact knapsack and orthogonal-packing subproblems, but maintaining validity and efficiency remains challenging (Iori et al. 2021).

Online Supplement PrecPack: An Efficient Open-Source Exact Solver for Bin · Appendix A: Additional Technical Details

The supplement is titled “PrecPack: An Efficient Open-Source Exact Solver for Bin Packing with Generalized Precedence Constraints” and lists seven authors. The supplied passages provide bibliographic identification but no additional technical details from Appendix A.

  • Online Supplement PrecPack: An Efficient Open-Source Exact Solver for Bin: The supplement presents PrecPack as an exact solver for bin packing with generalized precedence constraints.
  • Online Supplement PrecPack: An Efficient Open-Source Exact Solver for Bin: The title identifies the work as addressing bin packing with generalized precedence constraints.
  • Appendix A: Additional Technical Details: The supplied passages identify the work but do not provide technical content from Appendix A.
  • Online Supplement PrecPack: An Efficient Open-Source Exact Solver for Bin: Sunkanghong Wang, Zhengzhong Ricky You, and Roberto Baldacci are listed as authors.
  • Online Supplement PrecPack: An Efficient Open-Source Exact Solver for Bin: The supplied author information spans two passage entries, covering the complete seven-author list.
  • Online Supplement PrecPack: An Efficient Open-Source Exact Solver for Bin: Baichuan Mo, Hu Qin, Lijun Wei, and Zhou Xu are listed as additional authors.

A.1. DFF Candidates and Selection … A.7. C++ Identifiers in the Interface Diagram

The appendix specifies PrecPack’s implementation details for DFF-based bounds, conflict-aware relaxation, exact root certification, maximal-load branching, state-dependent bounds, memory management, and interface documentation. Together, these procedures preserve bound validity while controlling search effort and storage across generalized precedence cases.

  • A.2. Conflict-Aware BINLB: Conflict-aware BINLB proves infeasibility of packing residual items into UB−d−1 bins, using valid conflict edges, lower bounds, remembered results, and conflict-feasible recursive packing.Its conflict relaxation supplies a bound because every future-load sequence yields a capacity-feasible packing that respects the conflict graph; auxiliary feasible packings are not BPP-GP incumbents.
  • A.3. Integer Computation of the Root Lower Bound: Root lower-bound certification converts nonnegative floating-point dual values into checked integer profits, proves maximum pattern profit, and rounds the resulting ratio upward.The certification calculation separates heuristic column-generation stopping from final pricing, retains the previous bound if the integer optimum is unproved, and avoids relying on the restricted LP objective’s rounding.
  • A.4. Maximal-Load Enumeration: Maximal-load enumeration uses DFS with precedence-aware eligibility, capacity checks, dominance ordering, and a final scan that discards any load admitting a feasible superset.Zero-weight arcs can make successors eligible within a bin, whereas positive-weight arcs defer successors; the same procedure handles arbitrary nonnegative precedence weights and forced-empty transitions.
  • A.5. State-Dependent Precedence Bounds: State-dependent precedence bounds propagate unavailable-bin offsets and predecessor or successor restrictions to establish path, one-machine, and closure lower bounds.The path bound requires at least ei + ηi + 1 additional bins for each unassigned item, and unit precedence weights reduce it to the ordinary residual longest-path bound.
  • A.6. State Storage and Memory Accounting: State storage groups comparable records by assigned-item sets, supports depth-based queue updates with versioning, and accounts for replacement allocations before enforcing memory limits.If storage requirements exceed the limit, the search stops without discarding remembered states; precomputed masks and reused temporary arrays support closure and auxiliary bounds.
  • A.7. C++ Identifiers in the Interface Diagram: The interface documentation maps abbreviated Figure 2 labels to original C++ identifiers and clarifies that arrows represent selected dependencies rather than execution order.The Column Pricer seeks improving patterns, while the Certification Pricer computes maximum scaled profit over the full pattern set; both use 64-bit integer profits but may differ in scaling and stopping conditions.

Appendix B: Proofs · B.1. Proof of Proposition 1

The proof establishes that feasible partial packings with the same state admit identical next loads and equivalent future feasibility, regardless of their absolute depths. Therefore, their completion costs are equal.

  • B.1. Proof of Proposition 1: The two partial packings share the same unassigned items, fixed weights, capacity, and precedence arcs.Their assigned sets are predecessor-closed, preventing precedence arcs from unassigned items to assigned items.
  • B.1. Proof of Proposition 1: A subset is feasible for the next bin exactly when its capacity and positive- and zero-weight predecessor conditions are satisfied.The condition L ∩ D1 = ∅ accounts for active distance restrictions, while predecessor placement conditions enforce precedence feasibility.
  • B.1. Proof of Proposition 1: Consequently, the two partial packings admit exactly the same next loads, including the empty load while items remain.The proof identifies the same feasible choices despite the packings’ different histories.
  • B.1. Proof of Proposition 1: Advancing one depth updates earlier-predecessor restrictions from Dr to Dr+1, while a newly assigned predecessor satisfies tij > r.After removing assigned items, the resulting condition is precisely Equation (7).
  • B.1. Proof of Proposition 1: A common next load generates identical child states regardless of the two absolute depths.Induction over any finite sequence of future loads preserves feasibility decisions and assigned sets.
  • Appendix B: Proofs: Proposition 1 concludes that equivalent partial packings have equal completion costs, C(P) = C(P̃).The result follows by matching all feasible continuations, including the empty continuation when no items remain.

B.2. Proof of Proposition 2

The proof shows that a minimum-length feasible future-load sequence always begins with a load in L(S), handling separately the cases F(S)=∅ and F(S)≠∅.

  • Existence: A finite feasible sequence exists, so a minimum-length sequence L∈C(S) can be chosen.Place unassigned items individually in topological order, inserting finitely many empty bins; every item fits, and the assigned set is predecessor-closed.
  • Case F(S)=∅: If F(S)=∅, the first load of any feasible sequence must be empty, and therefore belongs to L(S).A nonempty first load would belong to F(S).
  • Case F(S)≠∅: If F(S)≠∅, choose a maximal load bL∈Max⊆F(S) containing the original first load and move its remaining items into that first position.The new first load is feasible, later loads remain capacity-feasible, precedence constraints remain satisfied, and removing trailing empty loads yields a sequence no longer than L beginning with bL∈L(S).
  • Conclusion: Because the transformed sequence is no longer than the minimum-length sequence L, it is also minimum-length, proving that some minimum-length sequence begins with a load in L(S).The conclusion covers both cases.

B.3. Proof of Proposition 3

The proof shows that state S dominates S′ by preserving every feasible load sequence while never increasing the resulting bin count. This follows from equal assigned-item sets, unchanged feasibility conditions, and componentwise monotonicity under transitions.

  • B.3. Proof of Proposition 3: S and S′ have identical unassigned items and predecessor relations, so every load sequence feasible from S′ is initially feasible from S.The first load avoids D′_1 and therefore D_1, while capacity and predecessor-closure conditions remain unchanged.
  • B.3. Proof of Proposition 3: Equation (7) is componentwise monotone, so each feasible load preserves the state inclusion through successor generation and item removal.Induction over the load sequence establishes that every sequence feasible from S′ is also feasible from S, including the empty sequence.
  • B.3. Proof of Proposition 3: For any sequence of k loads, S uses no more bins than S′ because d + k ≤ d′ + k, proving that S dominates S′.The argument applies to both nonempty and empty sequences.

B.4. Proof of Proposition 4

The proof shows that deleting item i from any feasible load sequence for S yields a feasible sequence for S+ with no more loads, establishing that S+ dominates S.

  • Proof of Proposition 4: Deleting i preserves capacity and leaves S+ with a larger assigned set whose predecessor-membership conditions are no more restrictive.The distance restriction imposed by i is already represented in D+, so the first original load omitting i remains feasible at S+.
  • Proof of Proposition 4: Componentwise tuple inclusion is preserved before, during, and after the load containing i, maintaining feasibility through all subsequent loads.The induction covers capacity and precedence conditions, including empty loads.
  • Proof of Proposition 4: Removing trailing empty loads produces a sequence eL in C(S+) with |eL| ≤ |L|, so S+ has an objective no larger than S and therefore dominates S.The conclusion uses d+ ≤ d together with the preserved feasibility of the transformed sequence.

B.5. Proof of Proposition 5

Proposition 5 is proved by transforming any feasible sequence beginning with a discarded load into a no-longer sequence beginning with a fixed feasible maximal load. Repeated replacements strictly increase a finite lexicographic order, so the process terminates at a nondiscarded load that dominates the original branch.

  • Proof construction: A fixed feasible maximal next load bL ⊇ L′ is chosen independently of the future-load sequence, and each sequence beginning with L is transformed to one beginning with bL without increasing length.The transformation first swaps i and j while preserving capacity and precedence feasibility, then moves every item in bL\L′ into the first bin; trailing empty bins are removed but intermediate empty bins remain.
  • Proof construction: The swap is precedence-feasible because moving i earlier relaxes outgoing constraints, moving j later relaxes incoming constraints, and θis ≥ θjs ensures j’s outgoing constraints remain satisfied.All other precedence constraints are unchanged, so the swapped sequence remains feasible.
  • Proof construction: Moving the remaining items of bL\L′ into the first bin preserves feasibility because that bin was chosen feasible, later bins lose weight, and moved-item arcs remain satisfied.Arcs with both endpoints moved or entering a moved item are satisfied in the first bin, while moving only a predecessor earlier cannot violate precedence.
  • Termination and dominance: Repeated replacements strictly increase the lexicographic order defined by W(L) and P in increasing item-index order, with a strict extension increasing total weight.The finite set of feasible maximal next loads therefore guarantees termination at a load not discarded by the rule.
  • Termination and dominance: By transitivity of dominance, the terminating nondiscarded load dominates the original one, so its corresponding branch can be discarded without losing an optimal solution.The same fixed bL applies to every original sequence, establishing dominance of the transformed sequence.

Appendix C: Experimental Settings · C.1. Computational Environments and Result Sources · C.2. Time-Limit Settings

Appendix C documents the computational environments and provenance of comparison results, then defines fixed PrecPack time limits using reference methods where reliable CPU ratings exist. It also records limitations that prevent direct normalization of computational effort across architectures and virtualized settings.

  • C.1. Computational Environments and Result Sources: PrecPack experiments used macOS 15.7.4 with optimized compiler options on a 14-core Apple M4 Pro, while processor ratings came from PassMark Software.The reported compiler options were -O3 -DNDEBUG -mcpu=native -flto.
  • C.1. Computational Environments and Result Sources: Published comparison results were collected from the cited tables, supplements, and companion results, with processor, memory, and thread details varying substantially across methods.Sources include Sewell and Jacobson (2012), Morrison et al. (2014), Otto et al. (2013), Li et al. (2020), Dell’Amico et al. (2012), Pereira (2016), Kramer et al. (2017), and Letelier et al. (2022).
  • C.1. Computational Environments and Result Sources: Some sources omit processor models or thread counts, and virtualized CPU ratings do not measure allocated performance, limiting reliable single-thread comparisons.This applies particularly to SALOME97, CPLEX and EA16 descriptions, and improved methods using virtual processors.
  • C.2. Time-Limit Settings: Time limits were fixed before experiments and calibrated per benchmark group against a selected reference set rather than all compared methods.For each reference method, the procedure uses its reported time limit and identifiable single-thread CPU rating, together with PrecPack’s rating RP = 4548.
  • C.2. Time-Limit Settings: The 350- and 1000-second comparisons target dedicated exact methods evaluated under longer limits, while CPLEX is excluded from reference sets because its shorter limit would constrain comparisons.CPLEX remains a published baseline despite weaker reported performance on harder instances.
  • C.2. Time-Limit Settings: Scholl BPP-P uses a fixed 1000-second limit because its processor descriptions cannot yield reliable single-thread ratings; other groups use nonempty reference sets.Tables C.1 and C.2 provide the reference-method calculations, benchmark-group sets, upper limits, and selected limits.
  • C.2. Time-Limit Settings: CPU ratings assess fixed-limit selection rather than normalize runtimes, so they do not establish equal computational effort across architectures, virtualization, or algorithms.The appendix explicitly treats these ratings as a calibration device, not as evidence of equivalent performance.
Loading 2609.17368v1…