Pattern based learning and optimisation through pricing for bin packing problem

Huayan Zhang, Ruibin Bai, Tie-Yan Liu, Jiawei Li, Bingchen Lin, Jianfeng RenarXiv 2024 · DOI · arXiv

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.

Comparison of Best Fit and Optimal solutions for two cases, illustrating the benefit of pattern-based packing.

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:

  1. Estimate: Kernel Density Estimation (KDE) forecasts the incoming item distribution.
  2. Plan: Column Generation identifies the optimal pattern set for the forecast.
  3. Pack: Arriving items are assigned to bins according to the plan.
  4. 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

Abstract

As a popular form of knowledge and experience, patterns and their identification have been critical tasks in most data mining applications. However, as far as we are aware, no study has systematically examined the dynamics of pattern values and their reuse under varying conditions. We argue that when problem conditions such as the distributions of random variables change, the patterns that performed well in previous circumstances may become less effective and adoption of these patterns would result in sub-optimal solutions. In response, we make a connection between data mining and the duality theory in operations research and propose a novel scheme to efficiently identify patterns and dynamically quantify their values for each specific condition. Our method quantifies the value of patterns based on their ability to satisfy stochastic constraints and their effects on the objective value, allowing high-quality patterns and their combinations to be detected. We use the online bin packing problem to evaluate the effectiveness of the proposed scheme and illustrate the online packing procedure with the guidance of patterns that address the inherent uncertainty of the problem. Results show that the proposed algorithm significantly outperforms the state-of-the-art methods. We also analysed in detail the distinctive features of the proposed methods that lead to performance improvement and the special cases where our method can be further improved.
BibTeX
@misc{zhang2024pattern,
  author = {Huayan Zhang and Ruibin Bai and Tie-Yan Liu and Jiawei Li and Bingchen Lin and Jianfeng Ren},
  title = {{Pattern based learning and optimisation through pricing for bin packing problem}},
  year = {2024},
  eprint = {2409.04456},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.04456},
}
Figure