Volume 14, Number 1, 117-135, DOI: 10.1007/s10601-008-9053-0

Efficient handling of universally quantified inequalities

Alexandre Goldsztejn, Claude Michel and Michel Rueher

From the issue entitled "Special Issue on Quantified CSPs and QBF; Guest Editors: Enrico Giunchiglia and Kostas Stergiou"

View Related Documents

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.

Keywords  Universally quantified inequalities - Branch and bound - Interval analysis

This paper is an extended version of a paper published at the SAC 2008 conference [15].

Fulltext Preview

Image of the first page of the fulltext document