×

Solving constraints over floating-point numbers. (English) Zbl 1067.68658

Walsh, Toby (ed.), Principles and practice of constraint programming - CP 2001. 7th international conference, Paphos, Cyprus, November 26 – December 1, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42863-1). Lect. Notes Comput. Sci. 2239, 524-538 (2001).
Summary: This paper introduces a new framework for tackling constraints over the floating-point numbers. An important application area where such solvers are required is program analysis (e.g., structural test case generation, correctness proof of numeric operations). Albeit the floating-point numbers are a finite subset of the real numbers, classical CSP techniques are ineffective due to the huge size of the domains. Relations that hold over the real numbers may not hold over the floating-point numbers. Moreover, constraints that have no solutions over the reals may hold over the floats. Thus, interval-narrowing techniques, which are used in numeric CSP, cannot safely solve constraints systems over the floats. We analyse here the specific properties of the relations over the floats. A CSP over the floats is formally defined. We show how local-consistency filtering algorithms used in interval solvers can be adapted to achieve a safe pruning of such CSP. Finally, we illustrate the capabilities of a CSP over the floats for the generation of test data.
For the entire collection see [Zbl 0984.00059].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: Link