Constraint-based very large-scale neighborhood search

(eng) A combinatorial optimization problem requires to take discrete decisions under constraints and optimizing a given objective function, such as planning, routing and scheduling problems. These problems arise in many industrial fields and are of economical significance. The general scope of this thesis is about Local Search (LS), that is an iterative methodology to solve combinatorial optimization problems. The principle is to generate a first solution, and to iteratively perform slight modifications to this solution in order to obtain a good score with respect to the objective function. Very Large-Scale Neighborhood (VLSN) is a sophisticated technique in Local Search to perform many modifications to the solutions at each iteration. These techniques have a greater visibility at each iteration and choose the next solution more efficiently. Very Large-Scale Neighborhoods have been successfully applied on many complex real-life problems. However VLSN are very hard to implement. This prevents the applicability of these techniques to new problems. This thesis aims at remedying this limitation and presents a framework that expresses VLSN search algorithms in terms of high-level components. VLSN search algorithms expressed by mean of our framework exhibits several benefits compared to existing approaches: 1) a more natural design of VLSN search algorithm, 2) a better reusability of existing components, 3) a greater adaptability to modifications to the problem to solve, and 4) a faster development of complex VLSN approaches. As a proof of concept, we implemented this framework. Experimental results show that our approach is comparable in time with respect to existing approaches, and that it allows to obtain state-of-the-art solutions on two real-life problems exhibiting different structure (one timetabling and one routing application). This validates that our approach is a helpful and efficient support to develop VLSN search algorithms on new and complex problems.