|
Validated Constraint Solving - Practicalities, Pitfalls, and
New Developments
We will concentrate on two themes:
- pitfalls in pure constraint propagation techniques, and
newer methods of overcoming these pitfalls, and
- robustness in constraint solving.
Many constraint propagation techniques iterate through the
constraints in a straightforward manner, but can fail because
they do not take account of the coupling between the
constraints. However, some methods of taking account of this
coupling are local in nature, and fail if the initial search
region is too large. We will discuss newer methods, based on
linear relaxations, that can often replace brute-force search by
solution of a large, sparse linear program.
Robustness has been recognized as important in geometric
computations and elsewhere for at least a decade, and more and
more developers are including validation in the design of their
systems. We will discuss work to-date in developing validated
versions of linear relaxations.
|
