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.
Born in 1954, R. Baker Kearfott received his Ph.D. in mathematics from the University of Utah in 1977, and has been on faculty of the University of Louisiana at Lafayette since then, and is presently a Professor of Mathematics.
His main interests are in validated solution of nonlinear systems, validated global optimization, and validated solution of constraint systems. He has published a monograph and has edited several conference proceedings on these subjects, while seven students have obtained Ph.D's under his direction. Software accomplishments in the area of validated constraints include three "ACM Transactions on Mathematical Software" articles and primary authorship of the "GlobSol" system for global optimization and constraint propagation.