Deep reinforcement learning improves one-dimensional bin packing efficiency
Deep Reinforcement Learning on Item-Compatibility Graphs for One-Dimensional Bin Packing
Machine LearningArtificial Intelligence
Summary
Packing items efficiently into fixed-size containers is a tough problem that many businesses face. The authors developed a method using deep reinforcement learning to decide which items to pack together by representing items as nodes in a graph. This model learns to combine items in ways that fit well, improving packing efficiency better than some traditional methods. Their approach works well right away on different sizes of packing problems without needing extra training.
What this means in practice
- •For logistics planners: Use the learned model to pack shipments more efficiently into containers of varying sizes, reducing wasted space and costs.
- •For cloud infrastructure managers: Optimize allocation of linear computing resources by treating workloads as items and servers as bins, improving utilization without custom solvers.
Authors
M. Aslı Aydın
Abstract
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.