# Pattern based learning and optimisation through pricing for bin packing problem

arXiv: https://arxiv.org/abs/2409.04456 · HTML: https://mlsanity.com/paper/2409.04456/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 42 references that are in the map.
- First posted on arXiv 27 Aug 2024.

## Builds on (most cited first, 9 of 9)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Online 3D Bin Packing with Constrained Deep Reinforcement Learning](https://mlsanity.com/paper/2006.14978/) (2020)
- [Analytics and Machine Learning in Vehicle Routing Research](https://mlsanity.com/paper/2102.10012/) (2021)
- [ORL: Reinforcement Learning Benchmarks for Online Stochastic Optimization Problems](https://mlsanity.com/paper/1911.10641/) (2019)
- [Attend2Pack: Bin Packing through Deep Reinforcement Learning with Attention](https://mlsanity.com/paper/2107.04333/) (2021)
- [Online Bin Packing with Predictions](https://mlsanity.com/paper/2102.03311/) (2021)
- [A Hybrid Pricing and Cutting Approach for the Multi-Shift Full Truckload Vehicle Routing Problem](https://mlsanity.com/paper/2012.06538/) (2020)
- [A Branch-and-Price Algorithm for the Temporal Bin Packing Problem](https://mlsanity.com/paper/1902.04925/) (2019)

## Abstract (arXiv)

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.