Search by Constraint PropagationReportar como inadecuado

Search by Constraint Propagation - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 1 Lifeware - Computational systems biology and optimization Inria Paris-Rocquencourt

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

Keywords : modeling languages constraint programming Horn clauses search

Autor: Thierry Martinez - François Fages - Sylvain Soliman -



Documentos relacionados