Search by Constraint Propagation

Thierry Martinez 1, * François Fages 1 Sylvain Soliman 1
* Corresponding author
Abstract : Constraint programming is traditionally viewed as the combination of two components: a constraint model and a search procedure. In this paper we show that tree search procedures can be fully inter-nalized in the constraint model with a fixed enumeration strategy. This approach has several advantages: 1) it makes search strategies declarative, and modeled as constraint satisfaction problems; 2) it makes it possible to express search strategies in existing front-end modeling languages supporting reified constraints without any extension ; 3) it opens up constraint propagation algorithms to search constraints and to the implementation of novel search procedures based on constraint propagation. We illustrate this approach with a Horn clause extension of the MiniZinc modeling language and the modeling in this language of a variety of search procedures, including dynamic symmetry breaking procedures and limited discrepancy search, as constraint satisfaction problems. We show that this generality does not come with a significant overhead, and can in fact exhibit exponential speedups over procedural implementations, thanks to the propagation of the search constraints..
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01140761
Contributor : Thierry Martinez <>
Submitted on : Thursday, April 9, 2015 - 2:07:09 PM
Last modification on : Monday, September 24, 2018 - 2:00:04 PM
Long-term archiving on : Tuesday, April 18, 2017 - 3:31:54 PM

File

MFS15ppdp.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Thierry Martinez, François Fages, Sylvain Soliman. Search by Constraint Propagation. PPDP '15- 17th International Symposium on Principles and Practice of Declarative Programming, Jul 2015, Siena, Italy. pp.173--183, ⟨10.1145/2790449.2790527⟩. ⟨hal-01140761⟩

Share

Metrics

Record views

260

Files downloads

194