New Light on Arc Consistency over Continuous Domains

Gilles Chabert 1 Gilles Trombettoni Bertrand Neveu
1 COPRIN - Constraints solving, optimization and robust interval analysis
CRISAM - Inria Sophia Antipolis - Méditerranée , ENPC - École des Ponts ParisTech
Abstract : Hyvönen and Faltings observed that propagation algorithms with continuous variables are computationally extremely inefficient when unions of intervals are used to precisely store refinements of domains. These algorithms were designed in the hope of obtaining the interesting property of arc consistency, that guarantees every value in domains to be consistent w.r.t. every constraint. In the first part of this report, we show that a pure backtrack-free filtering algorithm enforcing arc consistency will never exist. But surprisingly, we show that it is easy to obtain a property stronger than arc consistency with a few steps of bisection. We define this so-called box-set consistency and detail a generic method to enforce it. In the second part, a concrete algorithm, derived from the lazy version of the generic method is proposed. Correctness is proved and the properties are studied precisely.
Type de document :
Rapport
RR-5365, INRIA. 2004, pp.26
Liste complète des métadonnées

https://hal.inria.fr/inria-00070638
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 19 mai 2006 - 21:05:41
Dernière modification le : samedi 17 septembre 2016 - 01:27:12
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:37:53

Fichiers

Identifiants

  • HAL Id : inria-00070638, version 1

Collections

Citation

Gilles Chabert, Gilles Trombettoni, Bertrand Neveu. New Light on Arc Consistency over Continuous Domains. RR-5365, INRIA. 2004, pp.26. <inria-00070638>

Partager

Métriques

Consultations de
la notice

220

Téléchargements du document

145