TitleIncluding Soft Global Constraints in DCOPs
Publication TypeConference Paper
Year of Publication2012
AuthorsBessière C, Gutierrez P, Meseguer P
Conference Name18th International Conference on Principles and Practice of Constraint Programming (CP 2012)
Conference LocationQuébec, Canada
Date Published08/10/2012
Abstract

In the centralized context, global constraints have been essential for the advancement of constraint reasoning. In this paper we propose to include soft global constraints in distributed constraint optimization problems (DCOPs). Looking for efficiency, we study possible decompositions of global constraints, including the use of extra variables. We extend the distributed search algorithm BnB-ADOPT$^+$ to support these representations of global constraints. In addition, we explore the relation of global constraints with soft local consistency in DCOPs, in particular for the generalized soft arc consistency (GAC) level. We include specific propagators for the \emph{soft-all-different} and the \emph{soft-at-most} constraint and measure their impact in the solving process, providing empirical results on several benchmarks.