Efficient and Safe Global Constraints for Handling Numerical Constraint Systems

Abstract : Numerical constraint systems are often handled by branch and prune algorithms that combine splitting techniques, local consistencies, and interval methods. This paper first recalls the principles of Quad, a global constraint that works on a tight and safe linear relaxation of quadratic subsystems of constraints. Then, it introduces a generalization of Quad to polynomial constraint systems. It also introduces a method to get safe linear relaxations and shows how to compute safe bounds of the variables of the linear constraint system. Different linearization techniques are investigated to limit the number of generated constraints. QuadSolver, a new branch and prune algorithm that combines Quad, local consistencies, and interval methods, is introduced. QuadSolver has been evaluated on a variety of benchmarks from kinematics, mechanics, and robotics. On these benchmarks, it outperforms classical interval methods as well as constraint satisfaction problem solvers and it compares well with state-of-the-art optimization solvers.
Type de document :
Article dans une revue
SIAM Journal on Numerical Analysis, Society for Industrial and Applied Mathematics, 2005, 42 (5), pp. 2076-2097. <10.1137/S0036142903436174>
Liste complète des métadonnées

https://hal.inria.fr/hal-00907765
Contributeur : David Daney <>
Soumis le : jeudi 21 novembre 2013 - 17:07:20
Dernière modification le : mercredi 15 avril 2015 - 16:09:58

Identifiants

Collections

Citation

Yahia Lebbah, Claude Michel, Michel Rueher, David Daney, Jean-Pierre Merlet. Efficient and Safe Global Constraints for Handling Numerical Constraint Systems. SIAM Journal on Numerical Analysis, Society for Industrial and Applied Mathematics, 2005, 42 (5), pp. 2076-2097. <10.1137/S0036142903436174>. <hal-00907765>

Partager

Métriques

Consultations de la notice

149