Constraint-Based Very Large-Scale Neighborhood Search
(2012) Constraints : an international journal — Vol. 17, n° 2, p. 87-122 (2012)
Files
vlsn_constraints_20112.pdf
Open Access - Adobe PDF
- 995.33 KB
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Mouthuy, S., Van Hentenryck, P., & Deville, Y. (2012). Constraint-Based Very Large-Scale Neighborhood Search. Constraints : an international journal, 17(2), 87-122. https://hdl.handle.net/2078.5/253997 (Original work published 2012)