Abstract
Local search is a powerful and well-established method for solving hard combinatorial problems. Yet, until recently, it has provided very little user support, leading to time-consuming and error-prone implementation tasks. We introduce a scheme that, from a high-level description of a constraint in existential second-order logic with counting, automatically synthesises incremental penalty calculation algorithms. The performance of the scheme is demonstrated by solving real-life instances of a financial portfolio design problem that seem unsolvable in reasonable time by complete 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.
Similar content being viewed by others
References
Aarts, E., Lenstra, J.K. (eds.): Local Search in Combinatorial Optimization. John Wiley & Sons, Chichester (1997)
Ågren, M., Flener, P., Pearson, J.: Set variables and local search. In: Barták, R., Milano, M. (eds.) CPAIOR 2005. LNCS, vol. 3524, pp. 19–33. Springer, Heidelberg (2005)
Cadoli, M., Palopoli, L., Schaerf, A., Vasile, D.: NPSPEC: An executable specification language for solving all problems in NP. In: Gupta, G. (ed.) PADL 1999. LNCS, vol. 1551, pp. 16–30. Springer, Heidelberg (1999)
Crawford, J.M., Ginsberg, M., Luks, E., Roy, A.: Symmetry-breaking predicates for search problems. In: Proc. of KR 1996, pp. 148–159. Morgan Kaufmann, San Francisco (1996)
Fagin, R.: Contributions to the Model Theory of Finite Structures, PhD thesis, UC Berkeley, California, USA (1973)
Flener, P., Pearson, J., Ågren, M.: Introducing ESRA, a relational language for modelling combinatorial problems. In: Bruynooghe, M. (ed.) LOPSTR 2004. LNCS, vol. 3018, pp. 214–232. Springer, Heidelberg (2004)
Flener, P., Pearson, J., Reyna, L.G.: Financial portfolio optimisation. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 227–241. Springer, Heidelberg (2004)
Immerman, N.: Descriptive Complexity. Springer, Heidelberg (1998)
Mancini, T.: Declarative constraint modelling and specification-level reasoning. PhD thesis, Università degli Studi di Roma “La Sapienza”, Italy (2004)
Michel, L., Van Hentenryck, P.: Localizer: A modeling language for local search. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 237–251. Springer, Heidelberg (1997)
Michel, L., Van Hentenryck, P.: A constraint-based architecture for local search. ACM SIGPLAN Notices 37(11), 101–110 (2002); Proc. of OOPSLA 2002
Nareyek, A.: Using global constraints for local search. In: Constraint Programming and Large Scale Discrete Optimization. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, vol. 57, pp. 9–28. American Mathematical Society (2001)
Sivertsson, O.: Construction of synthetic CDO Squared. Master’s thesis, Computing Science, Department of Information Technology, Uppsala University, Sweden (2005)
Van Hentenryck, P.: The OPL Optimization Programming Language. MIT Press, Cambridge (1999)
Van Hentenryck, P., Michel, L., Liu, L.: Constraint-based combinators for local search. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 47–61. Springer, Heidelberg (2004)
Walser, J.P.: Integer Optimization by Local Search. LNCS, vol. 1637. Springer, Heidelberg (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ågren, M., Flener, P., Pearson, J. (2005). Incremental Algorithms for Local Search from Existential Second-Order Logic. In: van Beek, P. (eds) Principles and Practice of Constraint Programming - CP 2005. CP 2005. Lecture Notes in Computer Science, vol 3709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564751_7
Download citation
DOI: https://doi.org/10.1007/11564751_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29238-8
Online ISBN: 978-3-540-32050-0
eBook Packages: Computer ScienceComputer Science (R0)