Abstract
We present a general tool for encoding and solving optimization problems. Problems can be modeled using several paradigms and/or languages such as: Prolog, MiniZinc, and GECODE. Other paradigms can be included. Solution search is performed by a hybrid solver that exploits the potentiality of the Constraint Programming environment GECODE and of the Local Search framework EasyLocal++ for Large Neighborhood Search . The user can modify a set of parameters for guiding the hybrid search. In order to test the tool, we show the development phase of hybrid solvers on some benchmark problems. Moreover, we compare these solvers with other approaches, namely a pure Local Search, a pure constraint programming search, and with a state-of-the-art solver for constraint-based Local Search.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Aarts, E., Lenstra, J.K.: Local Search in Combinatorial Optimization. John Wiley & Sons, Chichester (1997)
Krzysztof, R.: Apt. In: Principles of Constraint Programming. Cambridge University Press, Cambridge (2003)
Cipriano, R., Di Gaspero, L., Dovier, A.: A Hybrid Solver for Large Neighborhood Search: Mixing Gecode and EasyLocal++. In: Blesa, M.J., Blum, C., Di Gaspero, L., Roli, A., Sampels, M., Schaerf, A. (eds.) HM 2009. LNCS, vol. 5818, pp. 141–155. Springer, Heidelberg (2009)
Cipriano, R., Dovier, A., Mauro, J.: Compiling and Executing Declarative Modeling Languages to Gecode. In: Garcia de la Banda, M., Pontelli, E. (eds.) ICLP 2008. LNCS, vol. 5366, pp. 744–748. Springer, Heidelberg (2008)
Di Gaspero, L., Schaerf, A.: Writing local search algorithms using EasyLocal++. In: Voß, S., Woodruff, D.L. (eds.) Optimization Software Class Libraries, OR/CS, Kluwer Academic Publisher, Boston (2002)
Di Gaspero, L., Schaerf, A.: EasyLocal++: An object-oriented framework for flexible design of local search algorithms. Software — Practice & Experience 33(8), 733–765 (2003)
Gamma, E., Helm, R., Johnson, R., Vlissides, J.: Design patterns: elements of reusable object-oriented software. Addison-Wesley Professional (1995)
Jaffar, J., Maher, M.J.: Constraint logic programming: A survey. Journal of Logic Programming 19/20, 503–581 (1994)
Marriot, K., Stuckey, P.J., De Koninck, L., Samulowitz, H.: An introduction to minizinc, http://www.g12.cs.mu.oz.au/minizinc/downloads/doc-1.3/minizinc-tute.pdf
McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A.J., Di Gaspero, L., Qu, R., Burke, E.K.: Setting the research agenda in automated timetabling: The second international timetabling competition. INFORMS Journal on Computing 22(1), 120–130 (2010)
Michel, L., Van Hentenryck, P.: The comet programming language and system. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 881–881. Springer, Heidelberg (2005) doi: 10.1007/11564751/119
Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: Towards a Standard CP Modelling Language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007)
Swedish Institute of Computer Science. Sicstus prolog, http://www.sics.se/sicstus.html
Shaw, P.: Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 417–431. Springer, Heidelberg (1998)
Gecode Team. Gecode: Generic constraint development environment, http://www.gecode.org
Gecode Team. Gecode reference documentation, http://www.gecode.org/doc-latest/reference/index.html
Gecode Team. Modeling and programming with gecode, http://www.gecode.org/doc-latest/MPG.pdf
Universität Heidelberg, Institut für Informatik. TSPLIB, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
Wolf, S., Merz, P.: Evolutionary Local Search for the Minimum Energy Broadcast Problem. In: van Hemert, J., Cotta, C. (eds.) EvoCOP 2008. LNCS, vol. 4972, pp. 61–72. Springer, Heidelberg (2008)
Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation 1(1), 67–82 (1997)
Pieter Wuille and Tom Schrijvers. Monadic Constraint Programming with Gecode. In: Proc. of ModRef 2009, Eighth International Workshop on Constraint Modelling and Reformulation, Lisbon, Portugal (September 2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Cipriano, R., Di Gaspero, L., Dovier, A. (2013). A Multi-paradigm Tool for Large Neighborhood Search. In: Talbi, EG. (eds) Hybrid Metaheuristics. Studies in Computational Intelligence, vol 434. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30671-6_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-30671-6_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30670-9
Online ISBN: 978-3-642-30671-6
eBook Packages: EngineeringEngineering (R0)