Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Thierry Martinez Connect in order to contact the contributor
Submitted on : Thursday, April 9, 2015 - 2:07:09 PM
Last modification on : Friday, January 21, 2022 - 3:19:41 AM
Long-term archiving on: : Tuesday, April 18, 2017 - 3:31:54 PM


Files produced by the author(s)




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⟩



Record views


Files downloads