An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem
From MaRDI portal
Publication:2030652
DOI10.1016/J.EJOR.2020.10.050zbMATH Open1487.90561arXiv2004.00963OpenAlexW3094979732MaRDI QIDQ2030652FDOQ2030652
Authors: Luc Libralesso, Florian Fontan 
Publication date: 7 June 2021
Published in: European Journal of Operational Research (Search for Journal in Brave)
Abstract: In this article, 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. The resulting program was ranked first among 64 participants. 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. We perform a comprehensive study of these components showing that each of them contributes to the algorithm global performances. 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. On these instances, it finds the best-known solutions very quickly.
Full work available at URL: https://arxiv.org/abs/2004.00963
Recommendations
- Solving a large cutting problem in the glass manufacturing industry
- Cut-and-solve: An iterative search strategy for combinatorial optimization problems
- Anytime heuristic search
- Evolutionary Computation in Combinatorial Optimization
- A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Discrete location and assignment (90B80)
Cites Work
- Title not available (Why is that?)
- An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
- A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint
- A population heuristic for constrained two-dimensional non-guillotine cutting
- A goal-driven approach to the 2D bin packing and variable-sized bin packing problems
- The two-dimensional bin packing problem with variable bin sizes and costs
- Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem
- A hybrid heuristic algorithm for the 2D variable-sized bin packing problem
- A block-based layer building approach for the 2D guillotine strip packing problem
- Heuristic for the rectangular strip packing problem with rotation of items
- Two-dimensional strip packing with unloading constraints
- Models and algorithms for three-stage two-dimensional bin packing
- Branch-and-price and beam search algorithms for the variable cost and size bin packing problem with optional items
- Solving the circular open dimension problem by using separate beams and look-ahead strategies
- Partial enumeration algorithms for two-dimensional bin packing problem with guillotine constraints
- Heuristics for the strip packing problem with unloading constraints
- Guillotine cutting of defective boards
- A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects
- A beam search approach to solve the convex irregular bin packing problem with guillotine guts
- Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem
- Two-stage two-dimensional guillotine cutting stock problems with usable leftover
- An open space based heuristic for the 2D strip packing problem with unloading constraints
- An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem
- A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects
- Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
- Two dimensional strip packing with unloading constraints
- Two dimensional knapsack with unloading constraints
Cited In (5)
- Exact approaches for the unconstrained two-dimensional cutting problem with defects
- A beam search algorithm for minimizing crane times in premarshalling problems
- A lookahead matheuristic for the unweighed variable-sized two-dimensional bin packing problem
- Exact and anytime approach for solving the time dependent traveling salesman problem with time windows
- Iterative beam search algorithms for the permutation flowshop
Uses Software
This page was built for publication: An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2030652)
