Weighted Constraint Satisfaction Problems with Min-Max Quantifiers
Lists
Only you see this
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...