Validated Constraint Solving—Practicalities, Pitfalls, and New Developments

Autor: R. Baker Kearfott
Rok vydání: 2005
Předmět:
Zdroj: Reliable Computing. 11:383-391
ISSN: 1573-1340
1385-3139
Popis: Many constraint propagation techniques iterate through the constraints in a straightforward manner, but can fai 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 put into perspective newer methods, based on linear relaxations, that can often replace brute-force search with the 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 provide citations to our work and to the work of others to-date in developing validated versions of linear relaxations. This work is in the form of a brief review and prospectus for future development. We give various simple examples to illustrate our points.
Databáze: OpenAIRE
Externí odkaz: