PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Reinforcement Learning on Item-Compatibility Graphs for One-Dimensional Bin Packing

M. Aslı Aydın

arXiv:2609.25397v1cs.LGcs.AImath.OC

TL;DR

Existing 1D approaches either predict an item ordering for heuristic placement or embed a bipartite GNN in a column-generation loop solving linear and integer programs at inference. The framework casts packing as edge merges on an item-compatibility graph and applies a size-invariant graph policy that transfers zero-shot across instance sizes. 2.31% versus FFD’s 2.66% mean gap across all 1,615 BPPLIB instances, with gains concentrated on structured, high-headroom families.

  • Problem

    Existing 1D approaches either predict an item ordering for heuristic placement or embed a bipartite GNN in a column-generation loop solving linear and integer programs at inference.

    Source: §1 · p. 3

  • Method

    The framework casts packing as edge merges on an item-compatibility graph and applies a size-invariant graph policy that transfers zero-shot across instance sizes.

    Source: §1 · p. 3

  • Results

    2.31% versus FFD’s 2.66% mean gap across all 1,615 BPPLIB instances, with gains concentrated on structured, high-headroom families.

    Source: §7 · p. 21

  • Takeaways & Limitations

    The policy improves on FFD on structured instances without per-instance search or hand-designed crossover, mutation, or repair operators.

    Source: §7 · p. 21

    The grouping genetic algorithm remains ahead on every family, and stochastic-beam inference takes longer than highly optimized heuristics such as FFD.

    Source: §6.2 · p. 21, §7 · p. 22

Abstract

from arXiv · show

The one-dimensional bin packing problem (1D-BPP) is a classical NP-hard combinatorial optimization problem with applications ranging from logistics and manufacturing to cloud resource management. Although deep reinforcement learning (DRL) has become a competitive paradigm for data-driven optimization, most learned packing methods target 2D and 3D variants, and intelligent learned solvers for 1D-BPP remain scarce. In this paper, we present a novel end-to-end, size-agnostic graph reinforcement learning framework for 1D-BPP. We formulate the packing process as a Markov decision process on an item-compatibility graph, serving as a structural knowledge representation in which every action merges two partial bins that fit together. A graph neural network actor-critic policy extracts relational features from this representation and is trained through reinforcement learning and decoded by stochastic beam search, enabling a single trained model to generalize zero-shot to instances of any size. We conduct a systematic empirical study across graph encoders, DRL algorithms, reward functions, training distributions, and hyperparameters. Evaluated zero-shot on the full BPPLIB benchmark against a constructive heuristic, a grouping genetic algorithm, and recent learned methods, our data-driven policy lowers the mean optimality gap of the constructive heuristic from 2.66\% to 2.31\%, with the largest gains on structured instances. Against learned baselines evaluated on the same benchmark, it attains a lower gap on most of the nine families and is far more stable across instance distributions. On the hardest benchmark family, it outperforms a state-of-the-art learned solver that relies on column generation and integer programming, while using no solver at all. A grouping genetic algorithm remains ahead overall, and we analyze where and why the residual gap arises.

1. Introduction

Learned solvers for 1D-BPP remain scarce, while existing approaches often rely on heuristic placement or mathematical-programming loops. This paper proposes a size-agnostic graph-RL solver and evaluates it against established and learned methods.

1. Introduction

  • The problem asks for the fewest identical capacity-C bins that can hold all items without exceeding capacity.Its applications include freight and supply chains, cutting stock, and server consolidation.Source: §1 · p. 2
  • Prior learned 1D-BPP approaches predict item order for heuristic placement or use a bipartite GNN with a column-generation and integer-programming loop.The paper notes that 1D instances lack coordinates or adjacency, while FFD is already near-optimal on average.Source: §1 · p. 3
  • The paper formulates packing as edge merges on an item-compatibility graph and uses a size-invariant graph policy for zero-shot transfer across instance sizes.Each action merges partial bins that fit together; node features use relative load and normalized degree.Source: §1 · p. 3
  • The paper positions its graph representation as structural knowledge that supports learned decisions without hand-crafted heuristic rules.It presents the trained policy as a potential decision component for recurring packing decisions made without a solver in the loop.Source: §1 · p. 3
  • The study compares three graph encoders and six RL algorithms, selecting design choices on in-distribution validation data rather than the benchmark.It evaluates a single uniform-trained model across complete BPPLIB families against FFD, a grouping genetic algorithm, and recent learned solvers.Source: §1 · pp. 3–4

2. Related work

Prior work spans exact and constructive methods, grouping metaheuristics, and learned solvers, with different trade-offs in quality, cost, and transfer. The paper motivates item-compatibility graphs as a direct state representation for learned 1D-BPP policies.

2.1. Exact and heuristic methods

  • Exact methods solve moderate instances efficiently, but effort grows sharply on instances with tight capacity structure; constructive heuristics, including FFD and BFD, remain the practical standard for real-time use.Source: §2.1 · p. 4

2.2. Grouping metaheuristics

  • Grouping genetic algorithms manipulate whole bins with group-level operators and remain the standard high-quality reference for 1D-BPP.Metaheuristics are comparatively expensive, offer no quality or convergence guarantees, and do not transfer learning across instances.Source: §2.2 · pp. 4–5

2.3. Learning-based methods for bin packing

  • Learned packing methods have focused mainly on 2D, 3D, and strip packing, while 1D approaches learn item order for a heuristic or use a GNN with column generation and integer programming [30].The paper notes that the one-dimensional problem has attracted little learning-based work.Source: §2.3 · p. 5

2.4. Graph representations of 1D-BPP

  • The item-compatibility graph represents items or partial bins as nodes and feasible pairwise merges as edges, making local graph updates a natural reinforcement-learning state.Unlike an arc-flow network whose size scales with capacity, this graph gives edges the direct meaning of feasible merges.Source: §2.4 · p. 5
  • The proposed MDP uses a size-independent state and assigns every packing decision to the learned policy rather than a heuristic placement rule or programming loop.The design is evaluated on the complete BPPLIB benchmark against constructive heuristics, grouping metaheuristics, and learned solvers.Source: §2.4 · p. 5

3. Problem definition

The paper defines 1D-BPP as assigning weighted items to the fewest capacity-limited bins, then represents feasible item pairs in an item-compatibility graph. A packing corresponds to capacity-feasible cliques in that graph.

3.1. One-dimensional bin packing problem

  • An instance consists of integer-weight items and a common bin capacity; each item is assigned to exactly one bin, and the objective is to minimize bins used.The integer-programming formulation uses binary variables for bin use and item placement.Source: §3.1 · p. 6

3.2. Item-compatibility graph

  • The item-compatibility graph joins item pairs whose combined weight fits within capacity, so a packing is a capacity-constrained partition into cliques.For the five-item example with C = 11, the graph has eight edges representing feasible pairs.Source: §3.2 · p. 6, Figure 1 · p. 7

4. Methods

Packing is formulated as a sequential edge-merge MDP on an item-compatibility graph. A size-independent GNN actor–critic is trained with reinforcement learning and decoded using stochastic beam search.

4.1. MDP formulation

  • Each state is a graph of partial bins, feasible merges are its edges, and maximizing merge rewards minimizes the final bin count.The episode ends when no compatible pair remains; merge order matters, as the example's alternative sequence reaches two bins instead of three.Source: §4.1 · pp. 7–8

4.2. DRL architecture

  • A three-layer message-passing GNN encodes the graph, and fixed-dimension state and edge readouts let one actor–critic handle graphs of any size.The actor scores feasible merges, while the critic predicts state value.Source: §4.2 · pp. 8–10

4.3. Training

  • The study trains several policy-gradient, actor–critic, and value-based algorithms; PPO is the primary configuration, selected using held-out validation performance.PPO updates use sampled episodes, reward-to-go advantages, and a clipped surrogate objective.Source: §4.3 · pp. 10–11

4.4. Inference: stochastic beam search

  • Stochastic beam search samples distinct merges for each partial solution, retains the best candidates by bin count and log-probability, and returns the completed solution with fewest bins.Sampling can explore merges with low but nonzero policy probability; decoding is deterministic for a given seed.Source: §4.4 · p. 12

5. Experiments and Results

The experiments use all nine complete BPPLIB families and compare the proposed solver with constructive, grouping-metaheuristic, and learned methods.

5.1. Benchmark instances

  • The benchmark comprises all instances from nine BPPLIB families, whose item counts, capacities, and weight structures vary and are out of distribution for training on uniform 50-item instances.Optimal or best-known values are taken from BPPLIB.Source: §5.1 · p. 12

5.2. Baselines and comparators

  • First-Fit Decreasing is the reference constructive heuristic; Best-Fit Decreasing matched it on validation data and is omitted from the tables.FFD sorts items in nonincreasing order and places each into the first feasible bin, as described in the background passage.Source: §5.2 · p. 13
  • The grouping genetic algorithm starts from FFD, BFD, and randomized first-fit packings, then applies grouping crossover and item-swap or item-move mutations under a two-second per-instance limit.The population contains 50 packings, with the best 10% carried over unchanged.Source: §5.2 · p. 13
  • Learned comparators include Shi et al.'s bipartite-GCN methods with column generation and three reported RL baselines: PTR, HRL-GPN, and RRMCTS.The bipartite-GCN comparisons include variants with and without the monotonicity cut.Source: §5.2 · p. 13

5.3. Metrics and evaluation protocol

The evaluation reports per-instance optimality gaps and related comparisons against fixed BPPLIB optima. Models are trained on uniform 50-item synthetic instances, with the primary configuration's hyperparameters listed in Table 2.

5.3. Metrics and evaluation protocol

  • Optimality gap is computed per instance as (bins used / BPPLIB optimum − 1) × 100%, with mean and standard deviation reported for each family.The optimum is the optimal or best-known BPPLIB value.Source: §5.3 · p. 14
  • The protocol also reports instances solved optimally and wins or losses against FFD; the proposed solver uses three decoding seeds, with gaps based on seed-averaged bin counts.Optimum counts use seed 0 unless stated otherwise, and gaps are independent of hardware.Source: §5.3 · p. 14

5.4. Implementation details

  • Models are trained for 2,000 epochs of 16 episodes on uniform weights from 1 to 100, with n = 50 and capacity C = 100; Table 2 lists primary-configuration hyperparameters.Training uses a single seed, 42.Source: §5.4 · p. 14, Table 2 · p. 14

5.5. Design study: encoder and learning algorithm

The design study selects GCN+PPO: it matches the strongest validation baselines, and GCN is chosen over a tied GAT model for simpler aggregation. This choice also agrees with performance across the full benchmark.

5.5. Design study: encoder and learning algorithm

  • GCN+PPO and GAT+PPO match the 26.20-bin validation baseline with zero variance across seeds, while other policy-gradient combinations finish 0.07–1.03 bins higher.DQN and SARSA are not considered further; under greedy decoding they use 27.10–30.05 bins.Source: §5.5 · pp. 14–15, Table 3 · p. 15
  • GCN+PPO is selected over tied GAT+PPO for its simpler, parameter-free aggregation and smoother training curve.PPO is selected because its validation performance reaches the strongest-baseline level.Source: §5.5 · p. 15
  • On the benchmark, GIN+PPO trails GCN+PPO on most families, supporting the validation-based encoder choice over selection on a narrow subset.GIN models led a small validation grid on Falkenauer T and Scholl 2, but that ranking did not hold across the benchmark.Source: §5.5 · p. 15

5.6. Results

The uniform-trained solver improves on FFD overall and on most benchmark families, with the clearest gains on structured instances and larger instances. It remains behind the grouping genetic algorithm and has mixed results against other learned solvers.

5.6. Results

  • 2.31% vs 2.66%: the proposed solver lowers FFD’s mean optimality gap across all 1,615 instances, improving on five families, tying two, and trailing two.It uses fewer bins than FFD on 291 instances and more on 170, with 1,154 ties; the GGA remains ahead on every family at 0.51% mean gap.Source: §5.6 · pp. 15–16, Table 4 · p. 16
  • The proposed solver’s largest family-level gain is on Falkenauer T, where its gap falls from 14.69% to 11.88%, while it ties FFD on every Schwerin 1 and Wäscher instance.On low-headroom Hard28 and Scholl 1, it is marginally worse than FFD; losses to FFD are by one bin on all but two benchmark instances.Source: §5.6 · pp. 15–16, Table 4 · p. 16
  • On Falkenauer T, the gap improvement over FFD persists from n = 60 to n = 501 at 2.6–2.9 percentage points, while Scholl 2 remains between 2.2% and 2.5%.The number of Scholl 2 instances won over FFD rises from 20 to 48; on low-headroom Scholl 1, FFD gains the advantage as item count grows.Source: §5.6 · pp. 16–17, Table 5 · p. 17
  • Against learned baselines, the proposed solver has a lower gap than PTR on six families and than HRL-GPN and RRMCTS on seven, while remaining below 1.3% on three families.It beats BGCN/BGCNMC on Falkenauer T, Scholl 2, and Falkenauer U, ties on Wäscher, and trails on Scholl 3 and the Schwerin families.Source: §5.6 · pp. 17–18, Table 6 · p. 18

5.7. Ablation studies

The ablations retain the objective-equivalent per-step reward and uniform training distribution, and find only a small validation benefit from hyperparameter tuning. These alternatives do not close the gap to the metaheuristic.

5.7.1. Reward function

  • 3.81%: shaped reward has a worse overall gap than FFD’s 2.66%, despite improving Falkenauer T from 11.88% to 10.47%.It degrades every other family, including Hard28 (5.49% vs 1.21%) and Scholl 1 (2.58% vs 0.51%), and finds 342 optima versus 729 for per-step reward; sparse terminal reward is never better than per-step reward.Source: §5.7.1 · pp. 18–19, Table 7 · p. 19

5.7.2. Training distribution

  • Neither mixed-curriculum training nor family-specific specialists outperform the uniform-trained model on the evaluated instances.The capped specialist reaches 14.17% on Scholl 2 versus 2.35% for the uniform model; the U[30, 100] specialist reaches 2.07% on Scholl 1 W4 versus 0.55%.Source: §5.7.2 · p. 19

5.7.3. Hyperparameter tuning

  • 0.04 bins: Optuna tuning improves the held-out validation objective by only 0.04 bins over defaults, and test-split differences remain within run-to-run variation.Across four repetitions of one configuration, variation reached 0.4 bins; the authors conclude the defaults are near-optimal and the gap to the metaheuristic is structural rather than a tuning issue.Source: §5.7.3 · pp. 19–20, Table 8 · p. 20

6. Discussion

The solver’s gains concentrate where FFD leaves room for improvement, especially on structured instances. The grouping genetic algorithm remains ahead, consistent with its whole-bin search operating at a higher level than the policy’s local merges.

6.1. The role of headroom

  • On the 820 instances where FFD is suboptimal, the proposed solver wins 291 and lowers mean gap from 5.25% to 4.35%; on the 795 FFD-optimal instances it cannot win by definition.The solver loses one bin on 133 FFD-optimal instances and ties on 662; its benefit is maintained on triplet-structured Falkenauer T up to n = 501.Source: §6.1 · pp. 20–21

6.2. Relation to metaheuristics and hybrid learned solvers

  • The GGA remains ahead on every family (0.51% vs 2.31% mean gap), and the examined reward, training, encoder, and hyperparameter changes do not close the gap.The authors attribute the residual difference to the GGA searching whole bins while the policy makes roughly n local pairwise decisions among Θ(n^2) candidates.Source: §6.2 · p. 21

7. Conclusions and future work

The single learned policy lowers FFD’s mean gap, with gains concentrated on structured, high-headroom families, while a grouping genetic algorithm remains ahead overall. The framework also offers compatibility-rule adaptation, but currently incurs higher inference time than optimized heuristics.

7. Conclusions and future work

  • 2.66% to 2.31%: the single model lowers FFD’s mean gap across all 1,615 instances of nine BPPLIB families, with gains concentrated on structured, high-headroom families.It also has lower gaps than a column-generation learned solver on three of nine jointly evaluated families and is more stable across distributions than hierarchical-RL and MCTS baselines.Source: §7 · p. 21
  • A grouping genetic algorithm remains ahead overall; the analysis attributes the residual gap to learning at a pairwise, constructive level rather than to tuning.Source: §7 · p. 21
  • The method sits between FFD, recommended when a few extra bins are tolerable, and grouping metaheuristics, recommended when best attainable quality is required.It improves FFD on structured instances without per-instance search or hand-designed crossover, mutation, or repair operators.Source: §7 · p. 21
  • Changing only the compatibility rule that defines graph edges can adapt the framework to constrained variants of bin packing.Source: §7 · p. 22
  • Inference time, particularly with stochastic beam search, is higher than that of highly optimized heuristics such as FFD.Source: §7 · p. 22
  • Future work could raise the learning level to item selection or whole-bin construction, accelerate graph updates or greedy decoding, and extend the framework to dynamic or stochastic settings.Item selection is described as reducing the action space from quadratic to linear in item count.Source: §7 · p. 22

Appendix A. Full design-study grids

Appendix A provides complete design-study grids underlying Section 5.5, including greedy decoding results across trained models and beam-decoding results on selected discriminating subsets.

Appendix A. Full design-study grids

  • The greedy grid covers six families and all trained models, while the beam grid gives per-model results on the selected Falkenauer T and Scholl 2 subsets.Source: Appendix A · p. 22
  • Table A.9 groups its rows into uniform-trained V1 models, mixed-trained V2 models, and a final Scholl 1-distribution generalist V3 model.Source: Appendix A · p. 23
  • Table A.9 shows that policy-gradient methods reproduce FFD almost exactly under greedy decoding, while SAC and value-based methods fall below it.Source: Table A.9 · p. 23
  • Table A.10 reports stochastic beam results with beam width 20 and three seeds for policy models on two discriminating families, with FFD and GGA references.The evaluated subsets are the first 20 Falkenauer T and first 15 Scholl 2 instances.Source: Appendix A · p. 22, Table A.10 · p. 24

Related papers

Loading 2609.25397v1…