Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleEfficient and Safe Global Constraints for Handling Numerical Constraint Systems
Author(s) David Daney, Yahia Lebbah, Jean-Pierre Merlet, Claude Michel, Michel Rueher
Textaccepted, Siam Journal on Numerical Analysis
TypeTechnical Report, Misc
AbstractNumerical 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 generalisation 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 linearisation 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 CSP solvers and it compares well with state-of-the-art optimisation solvers.
URL http://www.essi.fr/~rueher/
Translation No
Refereed No