–
March 21, 2019
Tree Search and the EURO/ROADEF 2018 Challenge
We present a simple and competitive heuristic Branch and Bound. It performs
heuristic cuts and pseudo-dominances to solve the EURO/ROADEF cutting glass
problem proposed by Saint-Gobain. It imports ideas from the AI Planning
community that are competitive with classical meta-heuristics. The resulting
program was ranked first over 20 qualified submissions in the final phase of
the challenge.
In this talk, we will describe the cutting glass problem, then introduce the
ideas from AI planning that can be relevant in Operations Research starting
from the basics and arrive to the state of the art. Finally, we will see how
to apply those ideas to the challenge problem.
Link to the challenge web page:
http://www.roadef.org/challenge/2018/en/finalResults.php
