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.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Abdullah, S., Ahmadi, S., Burke, E., & Dror, M. (2004). Applying ahuja-orlin’s large neighborhood for constructing examination timetabling solution. In Proceedings of the 5th international conference on the practice and theory of automated timetabling, no. 3616 in lecture notes in computer science (pp. 413–420). Springer.
Abdullah, S., Ahmadi, S., Burke, E., & Dror, M. (2007). Investigating ahuja-orlin’s large neighbourhood search approach for examination timetabling. OR Spectrum, 29, 351–372.
Abdullah, S., Ahmadi, S., Burke, E., Dror, M., & McCollum, B. (2007). A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem. Journal of the Operational Research Society, 58, 1494–1502.
Ahuja, R. K., Ergun, Ö., Orlin, J. B., & Punnen, A. P. (2002). A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123(1–3), 75–102.
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications, ed. Prentice Hall, United States (accepted for publication).
Ahuja, R. K., Orlin, J. B., & Sharma, D. (2001). Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem. Mathematical Programming, 91, 71–97.
Ahuja, R. K., Orlin, J. B., & Sharma, D. (2003). A composite Very Large-Scale Neighborhood structure for the capacitated minimum spanning tree problem. Operations Research Letters, 31, 185–194.
Benoist, T. (2010). Characterization and automation of matching-based neigborhood. In CPAIOR’10.
Bompadre, A., & Orlin, J. B. (2005). Using grammars to generate Very Large Scale Neighborhoods for the traveling salesman problem and other sequencing problems. Integer Programming and Combinatorial Optimization, 3509/2005, 437–451.
Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22, 251–256. ACM, ID: 359101.
Burkard, R. E., Deineko, V. G., & Woeginger, G. J. (1998). The travelling salesman and the pq-tree. Mathematics of Operations Research, 23, 613–623.
Carter, M., & Laporte, G. (1996). Recent developments in practical examination timetabling. Practice and theory of automated timetabling (pp. 1–21).
Cipriano, R., Gaspero, L., & Dovier, A. (2009). A hybrid solver for large neighborhood search: Mixing gecode and easylocal+ +. In M. J. Blesa, C. Blum, L. Gaspero, A. Roli, M. Sampels, & A. Schaerf (Eds.), Hybrid metaheuristics (Vol. 5818, pp. 141–155). Berlin, Heidelberg: Springer.
Ergun, O., & Orlin, J. B. (2006). A dynamic programming methodology in Very Large Scale Neighborhood search applied to the traveling salesman problem. Discrete Optimization, 3, 78–85.
Ergun, O., Orlin, J. B., & Steele-Feldman, A. (2002). Creating Very Large Scale Neighborhoods out of smaller ones by compounding moves: A study on the vehicle routing problem. Tech. Rep. 4393-02, MIT Sloan School of Management.
Esau, L. R., & Williams, K. C. (1966). On teleprocessing system design: Part II a method for approximating the optimal network. IBM Systems Journal, 5(3), 142–147.
Glover, F. (1996). Ejection chains with combinatorial leverage for the tsp. Discrete Applied Mathematics, 65, 223–253.
Hentenryck, P. V., & Michel, L. (2005). Constraint-Based Local Search. MIT Press.
Jha, K. C., Ahuja, R. K., & Şahin, G. (2008). New approaches for solving the block-to-train assignment problem. Networks, 51(1), 48–62.
Merlot, L., Boland, N., Hughes, B., & Stuckey, P. (2003). A hybrid algorithm for the examination timetabling problem. Practice and theory of automated timetabling IV (pp. 207–231).
Perron, L., Shaw, P., & Furnon, V. (2004). Propagation guided large neighborhood search. In M. Wallace (Ed.), Principles and practice of Constraint Programming—CP 2004 (Vol. 3258, pp. 468–481). Berlin, Heidelberg: Springer.
Solnon, C. (2000). Solving permutation constraint satisfaction problems with artificial ants. In Proceedings of the 14th European Conference on Artificial Intelligence (ECAI’2000) (pp. 118–122). Berlin.
Thompson, P. M. (1988). Local search algorithms for vehicle routing and other combinatorial problems. Ph.D. thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science.
Thompson, P. M., & Orlin, J. B. (1989). The theory of cyclic transfers. Tech. Rep. OR 200-89, Massachusetts Institute of Technology, Operations Research Center.
Thompson, P. M., & Psaraftis, H. N. (1993). Cyclic transfer algorithms for multivehicle routing and scheduling problems. Operations Research, 41, 935–946.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mouthuy, S., Hentenryck, P.V. & Deville, Y. Constraint-based Very Large-Scale Neighborhood search. Constraints 17, 87–122 (2012). https://doi.org/10.1007/s10601-011-9114-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-011-9114-7