Search by Constraint Propagation

Thierry Martinez 1, * François Fages 1 Sylvain Soliman 1
* Auteur correspondant
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..
Type de document :
Communication dans un congrès
ACM. PPDP '15- 17th International Symposium on Principles and Practice of Declarative Programming, Jul 2015, Siena, Italy. pp.173--183, 2015, 〈10.1145/2790449.2790527〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01140761
Contributeur : Thierry Martinez <>
Soumis le : jeudi 9 avril 2015 - 14:07:09
Dernière modification le : mardi 10 janvier 2017 - 17:36:03
Document(s) archivé(s) le : mardi 18 avril 2017 - 15:31:54

Fichier

MFS15ppdp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

167

Téléchargements de fichiers

69