An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem
From MaRDI portal
Publication:2030652
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.
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
Cites work
- scientific article; zbMATH DE number 783783 (Why is no real title available?)
- A MIP model and a biased random-key genetic algorithm 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
- A block-based layer building approach for the 2D guillotine strip packing problem
- A goal-driven approach to the 2D bin packing and variable-sized bin packing problems
- A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects
- A hybrid heuristic algorithm for the 2D variable-sized bin packing problem
- A population heuristic for constrained two-dimensional non-guillotine cutting
- A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint
- An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
- An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem
- An open space based heuristic for the 2D strip packing problem with unloading constraints
- Branch-and-price and beam search algorithms for the variable cost and size bin packing problem with optional items
- Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem
- Guillotine cutting of defective boards
- Heuristic for the rectangular strip packing problem with rotation of items
- Heuristics for the strip packing problem with unloading constraints
- Models and algorithms for three-stage two-dimensional bin packing
- Partial enumeration algorithms for two-dimensional bin packing problem with guillotine constraints
- Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
- Solving the circular open dimension problem by using separate beams and look-ahead strategies
- The two-dimensional bin packing problem with variable bin sizes and costs
- Two dimensional knapsack with unloading constraints
- Two dimensional strip packing with unloading constraints
- Two-dimensional strip packing with unloading constraints
- Two-stage two-dimensional guillotine cutting stock problems with usable leftover
- Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem
Cited in
(5)- Iterative beam search algorithms for the permutation flowshop
- 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
- Exact approaches for the unconstrained two-dimensional cutting problem with defects
- A beam search algorithm for minimizing crane times in premarshalling problems
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)
