Name
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 {\tt Quad}, a global constraint that works on a tight and safe linear relaxation of quadratic subsystems of constraints. Then, it introduces a generalization of {\tt 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. {\tt QuadSolver}, a new branch and prune algorithm that combines {\tt Quad}, local consistencies, and interval methods, is introduced. {\tt 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1137/S0036142903436174 | SIAM J. Numerical Analysis |
Keywords | Field | DocType |
tt quad,constraint system,handling numerical constraint systems,constraint programming,interval method,local consistency,systems of equations and inequalities,safe global constraints,global constraint,tt quadsolver,safe linear relaxation,safe rounding,constraint satisfaction problem solvers,interval arithmetic,numerical constraint system,reformulation linearization technique,linear constraint system,system of equations,constraint satisfaction problem | Constraint satisfaction,Mathematical optimization,Linear system,Constraint programming,Algorithm,Constraint satisfaction problem,Interval arithmetic,Mathematics,Numerical linear algebra,Linearization,Constrained optimization | Journal |
Volume | Issue | ISSN |
42 | 5 | 0036-1429 |
Citations | PageRank | References |
30 | 1.75 | 25 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yahia Lebbah | 1 | 115 | 19.34 |
| Claude Michel | 2 | 107 | 10.57 |
| Michel Rueher | 3 | 613 | 59.81 |
| David Daney | 4 | 202 | 17.35 |
| Jean-pierre Merlet | 5 | 819 | 100.43 |