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: Web page of the EURO/ROADEF 2018 Challenge