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)
EditionSpringer
Abstract

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: