Constraint-Based Very Large-Scale Neighborhood Search

Mouthuy, Sébastien [UCL] Van Hentenryck, Pascal [Brown University - USA] Deville, Yves [UCL]

Very Large-Scale Neighborhood (VLSN) search is the idea of using neighborhoods of exponential size to find high-quality solutions to complex optimization problems efficiently. However, so far, VLSN algorithms are essentially described and implemented in terms of low-level implementation concepts, preventing code reuse and extensibility which are trademarks of constraint-programming systems. This paper aims at remedying this limitation and proposes a constraint-based VLSN (CBVLSN) framework to describe VLSNs declaratively and compositionally. Its main innovations are the concepts of cycle-consistent MoveGraphs and compositional moves which make it possible to specify an application in terms of constraints and objectives and to derive a dedicated VLSN algorithm automatically. The constraint-based VLSN framework has been prototyped in COMET and its efficiency is shown to be comparable to dedicated implementations.