An anytime tree search algorithm for two-dimensional two- and three-staged guillotine packing problems

• URL: http://arxiv.org/abs/2004.02603v2
• Date: Mon, 20 Apr 2020 15:49:14 GMT
• Title: An anytime tree search algorithm for two-dimensional two- and three-staged guillotine packing problems
• Authors: Florian Fontan, Luc Libralesso
• Abstract summary: algorithm was ranked first among 64 participants. We generalize it and show that it is not only effective for the specific problem it was originally designed for, but is also very competitive. The algorithm is implemented in a new software package called Packingr.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: [libralesso_anytime_2020] proposed an anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem (https://www.roadef.org/challenge/2018/en/index.php). The resulting program was ranked first among 64 participants. In this article, we generalize it and show that it is not only effective for the specific problem it was originally designed for, but is also very competitive and even returns state-of-the-art solutions on a large variety of Cutting and Packing problems from the literature. We adapted the algorithm for two-dimensional Bin Packing, Multiple Knapsack, and Strip Packing Problems, with two- or three-staged exact or non-exact guillotine cuts, the orientation of the first cut being imposed or not, and with or without item rotation. The combination of efficiency, ability to provide good solutions fast, simplicity and versatility makes it particularly suited for industrial applications, which require quickly developing algorithms implementing several business-specific constraints. The algorithm is implemented in a new software package called PackingSolver.

Related papers

• A Neural Column Generation Approach to the Vehicle Routing Problem with Two-Dimensional Loading and Last-In-First-Out Constraints [3.9594431485015096]
  A vehicle routing problem with two-dimensional loading constraints (2L-CVRP) presents significant practical and algorithmic challenges. This article presents an exact algorithm that integrates advanced machine learning techniques, specifically a novel combination of attention and recurrence mechanisms. The proposed algorithm successfully resolves an open instance in the standard test-bed, demonstrating significant improvements brought about by the incorporation of machine learning models.
  arXiv  Detail & Related papers  (2024-06-18T09:58:29Z)
• Learning based 2D Irregular Shape Packing [29.044043493942013]
  2D irregular shape packing is a necessary step to arrange UV patches of a 3D model within a texture atlas for memory-efficient appearance rendering in computer graphics. We introduce a learning-assisted 2D irregular shape packing method that achieves a high packing quality with minimal requirements from the input. In order to efficiently deal with large problem instances with hundreds of patches, we train deep neural policies to predict nearly rectangular patch subsets.
  arXiv  Detail & Related papers  (2023-09-19T05:21:52Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• The Fifteen Puzzle- A New Approach through Hybridizing Three Heuristics Methods [15.91012934719906]
  Fifteen Puzzle problem is one of the most classical problems that have captivated mathematical enthusiasts for centuries. In this paper, Bidirectional A* (BA*) search algorithm with threes, such as Manhattan distance (MD), linear conflict (LC), and walking distance (WD) has been used. Our implementation of BA* search can significantly reduce the space complexity, and guarantee either optimal or near-optimal solutions.
  arXiv  Detail & Related papers  (2023-01-06T07:17:23Z)
• Comparing Heuristics, Constraint Optimization, and Reinforcement Learning for an Industrial 2D Packing Problem [58.720142291102135]
  Cutting and Packing problems are occurring in different industries with a direct impact on the revenue of businesses. Machine learning is increasingly used for solving such problems.
  arXiv  Detail & Related papers  (2021-10-27T15:47:47Z)
• RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
  We propose a highly parallel primal-dual algorithm for the multicut (a.k.a.magnitude correlation clustering) problem. Our algorithm produces primal solutions and dual lower bounds that estimate the distance to optimum. We can solve very large scale benchmark problems with up to $mathcalO(108)$ variables in a few seconds with small primal-dual gaps.
  arXiv  Detail & Related papers  (2021-09-04T10:33:59Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm. We prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution.
  arXiv  Detail & Related papers  (2021-06-08T00:57:59Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• 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)
• An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem [0.0]
  We present the anytime tree search algorithm we designed for the 2018 ROADEF/EURO challenge glass cutting problem proposed by the French company Saint-Gobain. Its key components are: a new search algorithm called Memory Bounded A* (MBA*) with guide functions, a symmetry breaking strategy, and a pseudo-dominance rule. In addition, we designed a second tree search algorithm fully based on the pseudo-dominance rule and dedicated to some of the challenge instances with strong precedence constraints.
  arXiv  Detail & Related papers  (2020-04-02T12:51:26Z)

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.