You are here

Multi-Objective Large Neighborhood Search

TitleMulti-Objective Large Neighborhood Search
Publication TypeConference Proceedings
Year of Conference2013
AuthorsSchaus, Pierre
EditorHartert, Renaud
Conference NameInternational Conference on Principles and Practice of Constraint Programming (CP)

Large neighborhood search (LNS) [25] is a framework that combines the expressiveness of constraint programming with the efficiency of local search to solve combinatorial optimization problems. This paper introduces an extension of LNS, called multi-objective LNS (MO-LNS), to solve multi-objective combi- natorial optimization problems ubiquitous in practice. The idea of MO-LNS is to maintain a set of nondominated solutions rather than just one best-so-far solu- tion. At each iteration, one of these solutions is selected, relaxed and optimized in order to strictly improve the hypervolume of the maintained set of nondom- inated solutions. We introduce modeling abstractions into the OscaR solver for MO-LNS and show experimentally the efficiency of this approach on various multi-objective combinatorial optimization problems.

Full text: