Machine Learning for the Multi-Dimensional Bin Packing Problem: Literature Review and Empirical Evaluation

• URL: http://arxiv.org/abs/2312.08103v1
• Date: Wed, 13 Dec 2023 12:39:25 GMT
• Title: Machine Learning for the Multi-Dimensional Bin Packing Problem: Literature Review and Empirical Evaluation
• Authors: Wenjie Wu, Changjun Fan, Jincai Huang, Zhong Liu and Junchi Yan
• Abstract summary: Bin Packing Problem (BPP) is a well-established optimization (CO) problem. In this article, we first formulate BPP, introducing its variants and practical constraints. Then, a comprehensive survey on machine learning for multi-dimensional BPP is provided.
• Score: 52.560375022430236
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Bin Packing Problem (BPP) is a well-established combinatorial optimization (CO) problem. Since it has many applications in our daily life, e.g. logistics and resource allocation, people are seeking efficient bin packing algorithms. On the other hand, researchers have been making constant advances in machine learning (ML), which is famous for its efficiency. In this article, we first formulate BPP, introducing its variants and practical constraints. Then, a comprehensive survey on ML for multi-dimensional BPP is provided. We further collect some public benchmarks of 3D BPP, and evaluate some online methods on the Cutting Stock Dataset. Finally, we share our perspective on challenges and future directions in BPP. To the best of our knowledge, this is the first systematic review of ML-related methods for BPP.

Related papers

• Evaluating the Energy Consumption of Machine Learning: Systematic Literature Review and Experiments [16.62572282726245]
  Monitoring, understanding, and optimizing the energy consumption of Machine Learning (ML) are various reasons why it is necessary to evaluate the energy usage of ML. There exists no universal tool that can answer this question for all use cases, and there may even be disagreement on how to evaluate energy consumption for a specific use case.
  arXiv  Detail & Related papers  (2024-08-27T15:08:06Z)
• Hypergraph Enhanced Knowledge Tree Prompt Learning for Next-Basket Recommendation [50.55786122323965]
  Next-basket recommendation (NBR) aims to infer the items in the next basket given the corresponding basket sequence. HEKP4NBR transforms the knowledge graph (KG) into prompts, namely Knowledge Tree Prompt (KTP), to help PLM encode the Out-Of-Vocabulary (OOV) item IDs. A hypergraph convolutional module is designed to build a hypergraph based on item similarities measured by an MoE model from multiple aspects.
  arXiv  Detail & Related papers  (2023-12-26T02:12:21Z)
• Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem [0.0]
  The Colored Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP) CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity. We propose an adaptation of BPPs and new algorithms for the CBPP.
  arXiv  Detail & Related papers  (2023-10-06T04:14:11Z)
• Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning [156.5667417159582]
  This paper proposes a novel model of sequential information design, namely the Markov persuasion processes (MPPs) Planning in MPPs faces the unique challenge in finding a signaling policy that is simultaneously persuasive to the myopic receivers and inducing the optimal long-term cumulative utilities of the sender. We design a provably efficient no-regret learning algorithm, the Optimism-Pessimism Principle for Persuasion Process (OP4), which features a novel combination of both optimism and pessimism principles.
  arXiv  Detail & Related papers  (2022-02-22T05:41:43Z)
• Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes [48.09817971375995]
  We introduce DPP-Batch Bayesian Optimization (DPP-BBO), a universal framework for inducing batch diversity in sampling based BO. We illustrate this framework by formulating DPP-Thompson Sampling (DPP-TS) as a variant of the popular Thompson Sampling (TS) algorithm and introducing a Markov Chain Monte Carlo procedure to sample.
  arXiv  Detail & Related papers  (2021-10-22T08:51:28Z)
• Exploration in two-stage recommender systems [79.50534282841618]
  Two-stage recommender systems are widely adopted in industry due to their scalability and maintainability. A key challenge of this setup is that optimal performance of each stage in isolation does not imply optimal global performance. We propose a method of synchronising the exploration strategies between the ranker and the nominators.
  arXiv  Detail & Related papers  (2020-09-01T16:52:51Z)
• A Survey on Large-scale Machine Learning [67.6997613600942]
  Machine learning can provide deep insights into data, allowing machines to make high-quality predictions. Most sophisticated machine learning approaches suffer from huge time costs when operating on large-scale data. Large-scale Machine Learning aims to learn patterns from big data with comparable performance efficiently.
  arXiv  Detail & Related papers  (2020-08-10T06:07:52Z)
• A Generalized Reinforcement Learning Algorithm for Online 3D Bin-Packing [7.79020719611004]
  We propose a Deep Reinforcement Learning (Deep RL) algorithm for solving the online 3D bin packing problem. The focus is on producing decisions that can be physically implemented by a robotic loading arm. We show that the RL-based method outperforms state-of-the-art online bin packings in terms of empirical competitive ratio and volume efficiency.
  arXiv  Detail & Related papers  (2020-07-01T13:02:04Z)
• Online 3D Bin Packing with Constrained Deep Reinforcement Learning [27.656959508214193]
  We solve a challenging yet practically useful variant of 3D Bin Packing Problem (3D-BPP) In our problem, the agent has limited information about the items to be packed into the bin, and an item must be packed immediately after its arrival without buffering or readjusting. We propose an effective and easy-to-implement constrained deep reinforcement learning (DRL) method under the actor-critic framework.
  arXiv  Detail & Related papers  (2020-06-26T13:28:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.