Local Search (LS), 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.
VLSN are very hard to implement, but a recent PhD thesis has demonstrated a framework that expresses VLSN search algorithms in terms of high-level components [Mout11].
VLSN search algorithms expressed by mean of this 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.
OscaR is an open source framework for operational research. It notably features an implementation of constraint-based local search engine, and a constraint programming engine.
The CBLS engine is an efficient implementation of the local search paradigm. It is already efficient, notably the seminal NQueen problem with 50.000 queens can be solved within ten seconds on a regular laptop, and scheduling over hundreds of tasks can be solved efficiently.
OscaR is written in Scala, a very productive programming language.
Oscar.cbls proposes notably a language for defining problems in a declarative way, and features a efficient model evaluation mechanism.
Goal of the Ms Thesis
The goal is to propose a clean, efficient, useable, and flexible implementation of VLSN on top of the OscaR.cbls framework. A demonstrator will also be required, for instance on routing problems. OscaR.cbls already includes a framework for solving routing problems through local search ; the demonstrator might build on, this framework.
The implementation, should it be of good quality, will be included in the upcoming releases of OscaR.cbls.
The work will be co-supervised by Renaud de Landtsheer. Ideally it will be combined with a internship in immersion at the CETIC Industrial Research Center and for which the student will get specific credits.
[Mout11] Sébastien Mouthuy, Constraint-Based Very Large-Scale Neighborhood Search, PhD Thesis, September 2011, UCL Belgium