zbMATH — the first resource for mathematics

Inner and outer approximations of existentially quantified equality constraints. (English) Zbl 1160.68546
Benhamou, Frédéric (ed.), Principles and practice of constraint programming – CP 2006. 12th international conference, CP 2006, Nantes, France, September 25–29, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-46267-5/pbk). Lecture Notes in Computer Science 4204, 198-212 (2006).
Summary: We propose a branch and prune algorithm that is able to compute inner and outer approximations of the solution set of an existentially quantified constraint where existential parameters are shared between several equations. While other techniques that handle such constraints need some preliminary formal simplification of the problem or only work on simpler special cases, our algorithm is the first pure numerical algorithm that can approximate the solution set of such constraints in the general case. Hence this new algorithm allows computing inner approximations that were out of reach until today.
For the entire collection see [Zbl 1141.68004].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI