The seminar run from 11am to 12pm. Please register online
Date: 11th July 2019
Luc LIBRALESSO, PhD Student at INPG,
Abdel-Malik BOUHASSOUN, master Trainee at INPG,
Vincent JOST, researcher at CNRS, Grenoble
Tree search methods (for example A* for shortest path problems and Beam Search in OR) are used in artificial intelligence and Operation Research to solve decision and optimization problems. OR practitioners however, usually consider local search methods as state of the art for NP-hard problems with exotic constraints. We present 2 study in which our tree searches algorithms outperformed the best known solutions. First the EURO-ROADEF Challenge 2019, proposed by Saint-Gobain, and dealing with 2D rectangles packing. Second, SOP (Sequential Ordering Problem, that is, Traveling Salesman Problem with precedence constraints). We also discuss a C++ framework that we develop and which allows quick design of tree search algorithms integrating concepts from branch and bounds like symmetry breaking, dominance and specific cuts.