Name
Abstract | ||
|---|---|---|
This article 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 often unable to achieve a significant pruning of the domains of the variables occurring in quadratic constraint 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. The Simplex algorithm is then used to narrow the domains. Since most implementations of the Simplex work with floating point numbers and thus, are unsafe, we provide a procedure to generate safe linearizations. We also exploit a procedure provided by Neumaier and Shcherbina to get a safe objective value when calling the Simplex algorithm. With these two procedures, we prevent the Simplex algorithm from removing any solution while filtering linear constraint systems. Experimental results on classical benchmarks show that this new algorithm yields a much more effective pruning of the domains than local consistency filtering algorithms. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/s10601-004-5307-7 | Constraints |
Keywords | Field | DocType |
quadratic constraint,safe linearizations,new algorithm yield,simplex work,quadratic constraints,local consistency,quadratic constraint system,rigorous global filtering algorithm,quadratic equation,simplex algorithm,classical benchmarks,linear constraint system,global constraints,effective pruning | Constraint satisfaction,Local consistency,Mathematical optimization,Simplex algorithm,Linear system,Algorithm,Quadratic equation,Filter (signal processing),Linear programming,Mathematics,Linearization | Journal |
Volume | Issue | ISSN |
10 | 1 | 1572-9354 |
Citations | PageRank | References |
14 | 0.69 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yahia Lebbah | 1 | 115 | 19.34 |
| Claude Michel | 2 | 107 | 10.57 |
| Michel Rueher | 3 | 613 | 59.81 |