Exploring declarative local-search neighbourhoods with constraint programming

Gustav Björdal; Pierre Flener; Justin Pearson; Peter J. Stuckey

doi:10.1007/978-3-030-30048-7_3

Exploring declarative local-search neighbourhoods with constraint programming

Gustav Björdal, Pierre Flener, Justin Pearson, Peter J. Stuckey

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

Abstract

Using constraint programming (CP) to explore a local-search neighbourhood was first tried in the mid 1990s. The advantage is that constraint propagation can quickly rule out uninteresting neighbours, sometimes greatly reducing the number actually probed. However, a CP model of the neighbourhood has to be handcrafted from the model of the problem: this can be difficult and tedious. That research direction appears abandoned since large-neighbourhood search (LNS) and constraint-based local search (CBLS) arose as alternatives that seem easier to use. Recently, the notion of declarative neighbourhood was added to the technology-independent modelling language MiniZinc, for use by any backend to MiniZinc, but currently only used by a CBLS backend. We demonstrate that declarative neighbourhoods are indeed technology-independent by using the old idea of CP-based neighbourhood exploration: we explain how to encode automatically a declarative neighbourhood into a CP model of the neighbourhood. This enables us to lift any CP solver into a local-search backend to MiniZinc. Our prototype is competitive with CP, CBLS, and LNS backends to MiniZinc.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming
Subtitle of host publication	25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings
Editors	Thomas Schiex, Simon de Givry
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	37-53
Number of pages	17
ISBN (Electronic)	9783030300487
ISBN (Print)	9783030300470
DOIs	https://doi.org/10.1007/978-3-030-30048-7_3
Publication status	Published - 2019
Event	International Conference on Principles and Practice of Constraint Programming 2019 - Stanford, Stamford, United States of America Duration: 30 Sep 2019 → 4 Oct 2019 Conference number: 25th https://cp2019.a4cp.org/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11802
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Principles and Practice of Constraint Programming 2019
Abbreviated title	CP 2019
Country	United States of America
City	Stamford
Period	30/09/19 → 4/10/19
Internet address	https://cp2019.a4cp.org/

Cite this

Björdal, G., Flener, P., Pearson, J., & Stuckey, P. J. (2019). Exploring declarative local-search neighbourhoods with constraint programming. In T. Schiex, & S. de Givry (Eds.), Principles and Practice of Constraint Programming : 25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings (pp. 37-53). (Lecture Notes in Computer Science ; Vol. 11802 ). Springer. https://doi.org/10.1007/978-3-030-30048-7_3

Björdal, Gustav ; Flener, Pierre ; Pearson, Justin ; Stuckey, Peter J. / Exploring declarative local-search neighbourhoods with constraint programming. Principles and Practice of Constraint Programming : 25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings. editor / Thomas Schiex ; Simon de Givry. Cham Switzerland : Springer, 2019. pp. 37-53 (Lecture Notes in Computer Science ).

@inproceedings{3c8e18b257be4546b88b35f74de0278b,

title = "Exploring declarative local-search neighbourhoods with constraint programming",

abstract = "Using constraint programming (CP) to explore a local-search neighbourhood was first tried in the mid 1990s. The advantage is that constraint propagation can quickly rule out uninteresting neighbours, sometimes greatly reducing the number actually probed. However, a CP model of the neighbourhood has to be handcrafted from the model of the problem: this can be difficult and tedious. That research direction appears abandoned since large-neighbourhood search (LNS) and constraint-based local search (CBLS) arose as alternatives that seem easier to use. Recently, the notion of declarative neighbourhood was added to the technology-independent modelling language MiniZinc, for use by any backend to MiniZinc, but currently only used by a CBLS backend. We demonstrate that declarative neighbourhoods are indeed technology-independent by using the old idea of CP-based neighbourhood exploration: we explain how to encode automatically a declarative neighbourhood into a CP model of the neighbourhood. This enables us to lift any CP solver into a local-search backend to MiniZinc. Our prototype is competitive with CP, CBLS, and LNS backends to MiniZinc.",

author = "Gustav Bj{\"o}rdal and Pierre Flener and Justin Pearson and Stuckey, {Peter J.}",

year = "2019",

doi = "10.1007/978-3-030-30048-7_3",

language = "English",

isbn = "9783030300470",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "37--53",

editor = "Thomas Schiex and {de Givry}, Simon",

booktitle = "Principles and Practice of Constraint Programming",

note = "International Conference on Principles and Practice of Constraint Programming 2019, CP 2019 ; Conference date: 30-09-2019 Through 04-10-2019",

url = "https://cp2019.a4cp.org/",

}

Björdal, G, Flener, P, Pearson, J & Stuckey, PJ 2019, Exploring declarative local-search neighbourhoods with constraint programming. in T Schiex & S de Givry (eds), Principles and Practice of Constraint Programming : 25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings. Lecture Notes in Computer Science , vol. 11802 , Springer, Cham Switzerland, pp. 37-53, International Conference on Principles and Practice of Constraint Programming 2019, Stamford, United States of America, 30/09/19. https://doi.org/10.1007/978-3-030-30048-7_3

Exploring declarative local-search neighbourhoods with constraint programming. / Björdal, Gustav; Flener, Pierre; Pearson, Justin; Stuckey, Peter J.

Principles and Practice of Constraint Programming : 25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings. ed. / Thomas Schiex; Simon de Givry. Cham Switzerland : Springer, 2019. p. 37-53 (Lecture Notes in Computer Science ; Vol. 11802 ).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Exploring declarative local-search neighbourhoods with constraint programming

AU - Björdal, Gustav

AU - Flener, Pierre

AU - Pearson, Justin

AU - Stuckey, Peter J.

N1 - Conference code: 25th

PY - 2019

Y1 - 2019

N2 - Using constraint programming (CP) to explore a local-search neighbourhood was first tried in the mid 1990s. The advantage is that constraint propagation can quickly rule out uninteresting neighbours, sometimes greatly reducing the number actually probed. However, a CP model of the neighbourhood has to be handcrafted from the model of the problem: this can be difficult and tedious. That research direction appears abandoned since large-neighbourhood search (LNS) and constraint-based local search (CBLS) arose as alternatives that seem easier to use. Recently, the notion of declarative neighbourhood was added to the technology-independent modelling language MiniZinc, for use by any backend to MiniZinc, but currently only used by a CBLS backend. We demonstrate that declarative neighbourhoods are indeed technology-independent by using the old idea of CP-based neighbourhood exploration: we explain how to encode automatically a declarative neighbourhood into a CP model of the neighbourhood. This enables us to lift any CP solver into a local-search backend to MiniZinc. Our prototype is competitive with CP, CBLS, and LNS backends to MiniZinc.

AB - Using constraint programming (CP) to explore a local-search neighbourhood was first tried in the mid 1990s. The advantage is that constraint propagation can quickly rule out uninteresting neighbours, sometimes greatly reducing the number actually probed. However, a CP model of the neighbourhood has to be handcrafted from the model of the problem: this can be difficult and tedious. That research direction appears abandoned since large-neighbourhood search (LNS) and constraint-based local search (CBLS) arose as alternatives that seem easier to use. Recently, the notion of declarative neighbourhood was added to the technology-independent modelling language MiniZinc, for use by any backend to MiniZinc, but currently only used by a CBLS backend. We demonstrate that declarative neighbourhoods are indeed technology-independent by using the old idea of CP-based neighbourhood exploration: we explain how to encode automatically a declarative neighbourhood into a CP model of the neighbourhood. This enables us to lift any CP solver into a local-search backend to MiniZinc. Our prototype is competitive with CP, CBLS, and LNS backends to MiniZinc.

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

U2 - 10.1007/978-3-030-30048-7_3

DO - 10.1007/978-3-030-30048-7_3

M3 - Conference Paper

AN - SCOPUS:85075756803

SN - 9783030300470

T3 - Lecture Notes in Computer Science

SP - 37

EP - 53

BT - Principles and Practice of Constraint Programming

A2 - Schiex, Thomas

A2 - de Givry, Simon

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Principles and Practice of Constraint Programming 2019

Y2 - 30 September 2019 through 4 October 2019

ER -

Björdal G, Flener P, Pearson J, Stuckey PJ. Exploring declarative local-search neighbourhoods with constraint programming. In Schiex T, de Givry S, editors, Principles and Practice of Constraint Programming : 25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings. Cham Switzerland: Springer. 2019. p. 37-53. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-030-30048-7_3

Access to Document

10.1007/978-3-030-30048-7_3

Link to publication in Scopus