Weighted Super Solutions for Constraint Programs

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 20

Constraint Satisfaction and Satisfiability

Super solutions to constraint programs guarantee that if a limited number of variables lose their values, repair solutions can be found by modifying a bounded number of assignments. However, in many application domains the classical super solutions framework is not expressive enough since it only reasons about the number of breaks in a solution and the number of changes that are necessary to find a repair. For example, in combinatorial auctions we may wish to guarantee that we can always find a repair solution whose revenue exceeds some threshold while limiting the cost associated with forming such a repair. In this paper we present the weighted super solution framework that involves two important extensions. Firstly, the set of variables that may lose their values is determined using a probabilistic approach enabling us to find repair solutions for assignments that are most likely to fail. Secondly, we include a mechanism for reasoning about the cost of repair. The proposed framework has been successfully used to find robust solutions to combinatorial auctions.