Quality over Quantity in Soft Constraints

Alexander Knapp, Alexander Schiendorfer, Wolfgang Reif

Quality over Quantity in Soft Constraints

Partial constraint satisfaction and soft constraints enable to deal with over-constrained problems in practice. Con- straint relationships have been introduced to provide a qualita- tive approach to specifying preferences over the constraints that should be satisfied. In contrast to quantitative approaches like weighted or fuzzy CSPs, the preferences just rely on a directed acyclic graph. The approach is particularly aimed at scenarios where soft-constraint problems stemming from several indepen- dently modeled agents have to be aggregated into one problem in a multi-agent system. Existing transformations into weighted CSP introduce unintended, additional preference decisions. We first illustrate the application of constraint relationships in a case study from energy management along with deficiencies of existing work. We then show how to embed constraint relationships into the soft- constraint frameworks of partial valuation structures and further c-semirings by means of free constructions. We finally provide a prototypical implementation of heuristics for the well-known branch-and-bound algorithm along with an empirical evaluation.
published 2014 in: Limassol, Zypern Proceedings of ICTAI 2014 - Special Track on SAT and CSP technologies

Publisher: IEEE



For questions regarding the publication, please contact!