Weighted Constraint Satisfaction Problems with Min-Max Quantifiers

Jimmy Ho-Man Lee, Terrence W. K. Mak, Justin Yip

Abstract

Soft constraints are functions returning costs, and are essential in modeling over-constrained and optimization problems. We are interested in tackling soft constrained problems with adversarial conditions. Aiming at generalizing the weighted and quantified constraint satisfaction frameworks, a Quantified Weighted Constraint Satisfaction Problem (QWCSP) consists 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 propose a complete solver which is based on alpha-beta pruning. QWCSPs are useful special cases of QCOP/QCOP+, and can be solved as a QCOP/QCOP+. Restricting our attention to only QWCSPs, we show empirically that our proposed solving techniques can better exploit problem characteristics than those developed for QCOP/QCOP+. Experimental results confirm the feasibility and efficiency of our proposals.
BibTeX
@inproceedings{lee2011weighted,
  author = {Jimmy Ho-Man Lee and Terrence W. K. Mak and Justin Yip},
  title = {{Weighted Constraint Satisfaction Problems with Min-Max Quantifiers}},
  booktitle = {ICTAI},
  year = {2011},
  doi = {10.1109/ictai.2011.121},
}

Loading related content...

Figure