Solver-independent large neighbourhood search

Jip J. Dekker, Maria Garcia de la Banda, Andreas Schutt, Peter J. Stuckey, Guido Tack

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

5 Citations (Scopus)

Abstract

The combination of large neighbourhood search (LNS) methods with complete search methods has proved to be very effective. By restricting the search to (small) areas around an existing solution, the complete method is often able to quickly improve its solutions. However, developing such a combined method can be time-consuming: While the model of a problem can be expressed in a high-level solver-independent language, the LNS search strategies typically need to be implemented in the search language of the target constraint solvers. In this paper we show how we can simplify this process by (a) extending constraint modelling languages to support solver-independent LNS search definitions, and (b) defining small solver extensions that allow solvers to implement these solver-independent LNS searches. Modellers can then implement an LNS search to be executed in any extended solver, by simply using the modelling language constructs. Experiments show that the resulting LNS searches only introduce a small overhead compared to direct implementations in the search language of the underlying solvers.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings
EditorsJohn Hooker
Place of PublicationCham Switzerland
PublisherSpringer
Pages81-98
Number of pages18
ISBN (Electronic)9783319983349
ISBN (Print)9783319983332
DOIs
Publication statusPublished - 2018
EventInternational Conference on Principles and Practice of Constraint Programming 2018 - Lille, France
Duration: 27 Aug 201831 Aug 2018
Conference number: 24th
http://cp2018.a4cp.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11008
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2018
Abbreviated titleCP 2018
CountryFrance
CityLille
Period27/08/1831/08/18
Internet address

Cite this

Dekker, J. J., de la Banda, M. G., Schutt, A., Stuckey, P. J., & Tack, G. (2018). Solver-independent large neighbourhood search. In J. Hooker (Ed.), Principles and Practice of Constraint Programming: 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings (pp. 81-98). (Lecture Notes in Computer Science ; Vol. 11008 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-319-98334-9_6