Abstract
The online Bin Packing Problem (BPP) presents a significant challenge in optimization, requiring immediate placement of items without knowledge of future arrivals. Traditional heuristics are often suboptimal, while modern reinforcement learning (RL) approaches struggle with distribution shifts. This paper introduces CGPP (Column Generation Plan-and-Pack), a framework that bridges Operations Research and data mining. By utilizing duality theory to calculate "shadow prices" for packing patterns, CGPP enables adaptive, pattern-based decision-making. Our evaluation across diverse benchmarks shows that CGPP consistently outperforms state-of-the-art RL and heuristics, particularly in non-stationary environments, reducing the optimality gap by up to 62%.
Introduction
The Bin Packing Problem (BPP) is a fundamental combinatorial optimization problem where items of various sizes must be packed into the minimum number of bins of fixed capacity. In the online variant, items arrive sequentially, and each must be assigned to a bin immediately.
Current solutions generally fall into two categories: simple heuristics and data-driven methods. Heuristics like "Best Fit" are computationally efficient but lack foresight regarding future item distributions. Conversely, Reinforcement Learning (RL) models can learn complex strategies but often act as "black boxes" that fail to generalize when the underlying item distribution changes. This research proposes CGPP to address these gaps by valuing packing patterns through mathematical rigor.
Methodology: The CGPP Framework
The core innovation of this work is the CGPP framework, which treats packing patterns as units of knowledge priced via Duality Theory.
Pattern-Based Reformulation
Instead of individual item placement, CGPP focuses on "patterns"—valid combinations of items that fit into a single bin. By identifying optimal patterns for a predicted distribution, the algorithm can make more informed packing decisions.
Column Generation and Shadow Pricing
CGPP employs Column Generation, a technique from Operations Research, to manage the vast space of possible patterns. It calculates shadow prices for each item type; a high shadow price indicates an item is difficult to pack under current conditions. These prices guide a sub-problem to generate new, high-value patterns dynamically.
The CGPP Loop
The framework operates in four stages:
- Estimate: Kernel Density Estimation (KDE) forecasts the incoming item distribution.
- Plan: Column Generation identifies the optimal pattern set for the forecast.
- Pack: Arriving items are assigned to bins according to the plan.
- React: If the actual distribution deviates significantly from the forecast (monitored via KL divergence), the system triggers a re-planning phase or reverts to a robust heuristic.
Experimental Evaluation
The authors tested CGPP against several benchmarks, including standard uniform/normal distributions, classic theoretical datasets (BW1, LW1, PP1), and non-stationary "periodic" datasets where distributions shift every 2,000 items.
Key Results
- Superiority over RL: CGPP significantly outperformed ORL (a leading RL approach), which often failed to adapt to distribution shifts.
- Efficiency: In uniform distribution tests, CGPP reduced the gap to optimality by 17% to 62% compared to the best-performing baseline.
- Robustness: In environments with shifting distributions, CGPP maintained stable fill rates (often exceeding 95%) by re-identifying optimal patterns in real-time.
Discussion and Key Insights
A critical finding is the "Overestimation Trap": overestimating future item counts is more detrimental than underestimating, as it leads to "unfilled" bins. CGPP mitigates this through a specific risk ratio ($w/e$). Furthermore, unlike RL policies, the patterns generated by CGPP are inherently interpretable, allowing human operators to understand and verify the packing logic.
Conclusion
CGPP offers a robust, mathematically grounded approach to the online bin packing problem. By combining predictive planning with reactive uncertainty handling, it achieves state-of-the-art performance and superior generalization. Future work will explore extending this framework to multi-dimensional packing (2D/3D) and other combinatorial optimization problems such as vehicle routing.
Summary updated