Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem

• URL: http://arxiv.org/abs/2310.04471v2
• Date: Mon, 8 Jul 2024 17:09:19 GMT
• Title: Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem
• Authors: Renan F. F. da Silva, Yulle G. F. Borges, Rafael C. S. Schouery,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Colored Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP). The CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity, minimizing the number of used bins and satisfying the constraint that two items of the same color cannot be packed side by side in the same bin. In this article, we proposed an adaptation of BPP heuristics and new heuristics for the CBPP. Moreover, we propose a set of fast neighborhood search algorithms for CBPP. These neighborhoods are applied in a meta-heuristic approach based on the Variable Neighborhood Search (VNS) and a matheuristic approach that combines linear programming with the meta-heuristics VNS and Greedy Randomized Adaptive Search (GRASP). The results indicate that our matheuristic is superior to VNS and that both approaches can find near-optimal solutions for a large number of instances, even for those with many items.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Machine Learning for the Multi-Dimensional Bin Packing Problem: Literature Review and Empirical Evaluation [52.560375022430236]
  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.
  arXiv  Detail & Related papers  (2023-12-13T12:39:25Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Hybrid Approach for Solving Real-World Bin Packing Problem Instances Using Quantum Annealers [0.8434687648198277]
  We introduce a hybrid quantum-classical framework for solving real-world three-dimensional Bin Packing Problems (Q4RealBPP) Q4RealBPP permits the solving of real-world oriented instances of 3dBPP, contemplating restrictions well appreciated by industrial and logistics sectors.
  arXiv  Detail & Related papers  (2023-03-01T14:04:50Z)
• Hybrid Quantum-Classical Heuristic for the Bin Packing Problem [0.8434687648198277]
  A hybrid classical-quantum approach is presented for dealing with the one-dimensional Bin Packing Problem (1dBPP) A classical computation subroutine builds complete solutions to the problem from the subsets given by the quantum subroutine. Being a hybrid solver, we have called our method H-BPP.
  arXiv  Detail & Related papers  (2022-04-12T09:05:27Z)
• Combinatorial Pure Exploration with Bottleneck Reward Function and its Extension to General Reward Functions [13.982295536546728]
  We study the Combinatorial Pure Exploration problem with the bottleneck reward function (CPE-B) under the fixed-confidence and fixed-budget settings. We present both fixed-confidence and fixed-budget algorithms, and provide the sample complexity lower bound for the fixed-confidence setting. In addition, we extend CPE-B to general reward functions (CPE-G) and propose the first fixed-confidence algorithm for general non-linear reward functions with non-trivial sample complexity.
  arXiv  Detail & Related papers  (2021-02-24T06:47:51Z)
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation [70.41056265629815]
  When developing an algorithm for optimization, it is commonly assumed that parameters such as edge weights are exactly known as inputs. In this article, we review recently proposed techniques for pure exploration problems with limited feedback.
  arXiv  Detail & Related papers  (2020-12-31T12:40:52Z)
• 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)
• Adaptive Large Neighborhood Search for Circle Bin Packing Problem [8.855116523397935]
  We address a new variant of packing problem called the circle bin packing problem (CBPP) CBPP is to find a dense packing of circle items to multiple square bins so as to minimize the number of used bins. We propose an adaptive large neighborhood search (ALNS) algorithm, which uses our Greedy Algorithm with Corner Occupying Action (GACOA) to construct an initial layout.
  arXiv  Detail & Related papers  (2020-01-20T10:14:15Z)

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.