Quantified Weighted Constraint Satisfaction Problems
Wai Keung Terrence · 2011
Soft constraints are functions returning costs, and are essential in modeling over-constrained and optimization problems. Weighted constraint satisfaction is a soft constraint framework, aiming to find a complete assignment with minimum costs. Recently, we are interested in exploring constraint frameworks with adversaries. Quantified constraint satisfaction, which associates ∃ and ∀ quantifiers with vari-ables, is one of these frameworks. We are interested in tackling soft constrained problems with adversarial con-ditions. Aiming at generalizing the weighted and quantified constraint satisfaction frameworks, a Quantified Weighted Constraint Satisfaction Problem (QWCSP) con-sists of a set of finite domain variables, a set of soft constraints, and a min or max quantifier associated with each of these variables. We formally define QWCSP, and give examples to show how we compute the costs we desire. We give a complete solver based on alpha-beta pruning, followed by discus-sions on the general pruning conditions allowing us to further prune the search