Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

A Global Filtering Algorithm for Handling Systems of Quadratic Equations and Inequations

Yahia LebbahContact Information, Michel RueherContact Information and Claude MichelContact Information

(5)  Université de Nice-Sophia Antipolis, I3S-CNRS, 930 route des Colles, B.P. 145, 06903 Sophia Antipolis Cedex, France
(6)  Département d’Informatique, Université d’Oran, 31000 Oran, Algeria
Abstract
This paper introduces a new filtering algorithm for handling systems of quadratic equations and inequations. Such constraints are widely used to model distance relations in numerous application areas ranging from robotics to chemistry. Classical filtering algorithms are based upon local consistencies and thus, are unable to achieve a significant pruning of the domains of the variables occurring in quadratic constraints systems. The drawback of these approaches comes from the fact that the constraints are handled independently. We introduce here a global filtering algorithm that works on a tight linear relaxation of the quadratic constraints. First experimentations show that this new algorithm yields a much more effective pruning of the domains than local consistency filtering algorithms.

Contact Information Yahia Lebbah
Email: ylebbah@yahoo.fr

Contact Information Michel Rueher
Email: rueher@essi.fr

Contact Information Claude Michel
Email: cpjm@essi.fr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
2 newer articles

  1. Borradaile, Glencora (2005) Safe and tight linear estimators for global optimization. Mathematical Programming 102(3)
    [CrossRef]
  2. Lebbah, Yahia (2005) A Rigorous Global Filtering Algorithm for Quadratic Constraints*. Constraints 10(1)
    [CrossRef]
Remote Address: 38.107.191.108 • Server: mpweb04
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)