Efficient tree-search algorithms in Optimization and Operation Research - Naver Labs Europe
loader image

Grenoble INP logoThe 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

CNRS LogoAbstract:
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.



Ceci correspond à une petite biographie d'environ 200 caractéres