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

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.

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
Dekker, Jip J. ; de la Banda, Maria Garcia ; Schutt, Andreas ; Stuckey, Peter J. ; Tack, Guido. / Solver-independent large neighbourhood search. Principles and Practice of Constraint Programming: 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings. editor / John Hooker. Cham Switzerland : Springer, 2018. pp. 81-98 (Lecture Notes in Computer Science ).
@inproceedings{b62a0d6363e84ff6a2e9346ed624b2f9,
title = "Solver-independent large neighbourhood search",
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.",
author = "Dekker, {Jip J.} and {de la Banda}, {Maria Garcia} and Andreas Schutt and Stuckey, {Peter J.} and Guido Tack",
year = "2018",
doi = "10.1007/978-3-319-98334-9_6",
language = "English",
isbn = "9783319983332",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "81--98",
editor = "Hooker, {John }",
booktitle = "Principles and Practice of Constraint Programming",

}

Dekker, JJ, de la Banda, MG, Schutt, A, Stuckey, PJ & 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. Lecture Notes in Computer Science , vol. 11008 , Springer, Cham Switzerland, pp. 81-98, International Conference on Principles and Practice of Constraint Programming 2018, Lille, France, 27/08/18. https://doi.org/10.1007/978-3-319-98334-9_6

Solver-independent large neighbourhood search. / Dekker, Jip J.; de la Banda, Maria Garcia; Schutt, Andreas; Stuckey, Peter J.; Tack, Guido.

Principles and Practice of Constraint Programming: 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings. ed. / John Hooker. Cham Switzerland : Springer, 2018. p. 81-98 (Lecture Notes in Computer Science ; Vol. 11008 ).

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

TY - GEN

T1 - Solver-independent large neighbourhood search

AU - Dekker, Jip J.

AU - de la Banda, Maria Garcia

AU - Schutt, Andreas

AU - Stuckey, Peter J.

AU - Tack, Guido

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85053152651&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-98334-9_6

DO - 10.1007/978-3-319-98334-9_6

M3 - Conference Paper

SN - 9783319983332

T3 - Lecture Notes in Computer Science

SP - 81

EP - 98

BT - Principles and Practice of Constraint Programming

A2 - Hooker, John

PB - Springer

CY - Cham Switzerland

ER -

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