A Box-Consistency Contractor Based on Extremal Functions

Gilles Trombettoni 1 Yves Papegay 2 Gilles Chabert 3 Odile Pourtallier 4
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 HEPHAISTOS - HExapode, PHysiologie, AssISTance et Objets de Service
CRISAM - Inria Sophia Antipolis - Méditerranée
3 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
4 COPRIN - Constraints solving, optimization and robust interval analysis
CRISAM - Inria Sophia Antipolis - Méditerranée , ENPC - École des Ponts ParisTech
Abstract : Interval-based methods can approximate all the real solutions of a system of equations and inequalities. The Box interval constraint propagation algorithm enforces Box consistency. Its main procedure BoxNarrow handles one function f corresponding to the revised constraint, and one variable x, replacing the other variables of f by their current intervals. This paper proposes an improved BoxNarrow procedure for narrowing the domain of x when f respects certain conditions. In particular, these conditions are fulfilled when f is polynomial. f is first symbolically rewritten into a new form g. A narrowing step is then run on the non-interval extremal functions that enclose the interval function g. The corresponding algorithm is described and validated on several numerical constraint systems.
Type de document :
Communication dans un congrès
CP'10 - 16th International Conference on Principles and Practice of Constraint Programming, 2010, St Andrews, United Kingdom. 2010, <10.1007/978-3-642-15396-9_39>
Liste complète des métadonnées

https://hal.inria.fr/hal-01146875
Contributeur : Gilles Chabert <>
Soumis le : mercredi 29 avril 2015 - 12:00:56
Dernière modification le : mercredi 13 avril 2016 - 01:09:37

Fichier

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

Identifiants

Citation

Gilles Trombettoni, Yves Papegay, Gilles Chabert, Odile Pourtallier. A Box-Consistency Contractor Based on Extremal Functions. CP'10 - 16th International Conference on Principles and Practice of Constraint Programming, 2010, St Andrews, United Kingdom. 2010, <10.1007/978-3-642-15396-9_39>. <hal-01146875>

Partager

Métriques

Consultations de
la notice

211

Téléchargements du document

73