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 | |
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/Territory | United States of America |
City | Stamford |
Period | 30/09/19 → 4/10/19 |
Internet address |