Efficient handling of universally quantified inequalities |
| |
Authors: | Alexandre Goldsztejn Claude Michel Michel Rueher |
| |
Affiliation: | (1) LINA, University of Nantes, CNRS, Nantes, France;(2) I3S-CNRS, University of Nice-Sophia Antipolis, Nice, France |
| |
Abstract: | This paper introduces a new framework for solving quantified constraint satisfaction problems (QCSP) defined by universally
quantified inequalities on continuous domains. This class of QCSPs has numerous applications in engineering and technology.
We introduce a generic branch and prune algorithm to tackle these continuous CSPs with parametric constraints, where the pruning
and the solution identification processes are dedicated to universally quantified inequalities. Special rules are proposed
to handle the parameter domains of the constraints. The originality of our framework lies in the fact that it solves the QCSP
as a non-quantified CSP where the quantifiers are handled locally, at the level of each constraint. Experiments show that
our algorithm outperforms the state of the art methods based on constraint techniques.
This paper is an extended version of a paper published at the SAC 2008 conference 15]. |
| |
Keywords: | Universally quantified inequalities Branch and bound Interval analysis |
本文献已被 SpringerLink 等数据库收录! |
|