Adaptive Large Neighborhood Search for Circle Bin Packing Problem

• URL: http://arxiv.org/abs/2001.07709v1
• Date: Mon, 20 Jan 2020 10:14:15 GMT
• Title: Adaptive Large Neighborhood Search for Circle Bin Packing Problem
• Authors: Kun He, Kevin Tole, Fei Ni, Yong Yuan, Linyun Liao
• Abstract summary: 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.
• Score: 8.855116523397935
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address a new variant of packing problem called the circle bin packing problem (CBPP), which is to find a dense packing of circle items to multiple square bins so as to minimize the number of used bins. To this end, we propose an adaptive large neighborhood search (ALNS) algorithm, which uses our Greedy Algorithm with Corner Occupying Action (GACOA) to construct an initial layout. The greedy solution is usually in a local optimum trap, and ALNS enables multiple neighborhood search that depends on the stochastic annealing schedule to avoid getting stuck in local minimum traps. Specifically, ALNS perturbs the current layout to jump out of a local optimum by iteratively reassigns some circles and accepts the new layout with some probability during the search. The acceptance probability is adjusted adaptively using simulated annealing that fine-tunes the search direction in order to reach the global optimum. We benchmark computational results against GACOA in heterogeneous instances. ALNS always outperforms GACOA in improving the objective function, and in several cases, there is a significant reduction on the number of bins used in the packing.

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)
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
  We compare 8 popular numerical black-box optimization algorithms on the $L_infty$ star discrepancy problem. We show that all used solvers perform very badly on a large majority of the instances. We suspect that state-of-the-art numerical black-box optimization techniques fail to capture the global structure of the problem.
  arXiv  Detail & Related papers  (2023-06-29T14:57:56Z)
• Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem [18.19836641663039]
  We propose a novel algorithm combining evolutionary computation with the exact algorithm to solve the 0-1 MKP. It maintains a set of solutions and utilizes the information from the population to extract good partial assignments. It finds better solutions than the existing algorithms and provides new lower bounds for 10 large and hard instances.
  arXiv  Detail & Related papers  (2022-10-08T05:11:47Z)
• An Improved Greedy Algorithm for Subset Selection in Linear Estimation [5.994412766684842]
  We consider a subset selection problem in a spatial field where we seek to find a set of k locations whose observations provide the best estimate of the field value at a finite set of prediction locations. One approach for observation selection is to perform a grid discretization of the space and obtain an approximate solution using the greedy algorithm. We propose a method to reduce the computational complexity by considering a search space consisting only of prediction locations and centroids of cliques formed by the prediction locations.
  arXiv  Detail & Related papers  (2022-03-30T05:52:16Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Stagnation Detection in Highly Multimodal Fitness Landscapes [0.0]
  Stagnation detection has been proposed as a mechanism for randomized searchs to escape from local optima. In this paper, we investigate a new mechanism called radius memory which can be added to stagnation detection to control the search radius more carefully. We implement this idea in an algorithm called SD-RLS$textm$ and show compared to previous variants of stagnation detection that it yields speed-ups.
  arXiv  Detail & Related papers  (2021-04-09T14:33:52Z)
• CobBO: Coordinate Backoff Bayesian Optimization [45.53400129323848]
  We introduce Coordinate Backoff Bayesian Optimization (CobBO) to capture a smooth approximation of the global landscape. CobBO finds solutions comparable to or better than other state-of-the-art methods for dimensions ranging from tens to hundreds.
  arXiv  Detail & Related papers  (2021-01-13T15:39:32Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Stochastic Item Descent Method for Large Scale Equal Circle Packing Problem [22.230497408207594]
  gradient descent (SGD) is a powerful method for large-scale optimization problems in the area of machine learning. We apply SGD with batch selection of samples to a classic optimization problem in decision version. Specifically, we propose a item descent method (SIDM) for ECPP in large scale, which randomly divides the unit circles into batches.
  arXiv  Detail & Related papers  (2020-01-22T02:40:31Z)

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.