Exploring declarative local-search neighbourhoods with constraint programming

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-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 languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings
EditorsThomas Schiex, Simon de Givry
Place of PublicationCham Switzerland
PublisherSpringer
Pages37-53
Number of pages17
ISBN (Electronic)9783030300487
ISBN (Print)9783030300470
DOIs
Publication statusPublished - 2019
EventInternational Conference on Principles and Practice of Constraint Programming 2019 - Stanford, Stamford, United States of America
Duration: 30 Sep 20194 Oct 2019
Conference number: 25th
https://cp2019.a4cp.org/

Publication series

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

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2019
Abbreviated titleCP 2019
CountryUnited States of America
CityStamford
Period30/09/194/10/19
Internet address

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