Weighted Super Solutions for Constraint Programs

Alan Holland, Barry O'Sullivan

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.

Content Area: 6. Constraint Satisfaction and Satisfiability

Subjects: 15.2 Constraint Satisfaction

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.