QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems

Ulrich Junker

Over-constrained problems can have an exponential number of conflicts, which explain the failure, and an exponential number of relaxations, which restore the consistency. A user of an interactive application, however, desires explanations and relaxations containing the most important constraints. To address this need, we define preferred explanations and relaxations based on user preferences between constraints and we compute them by a generic method which works for arbitrary CP, SAT, or DL solvers. We significantly accelerate the basic method by a divide-and-conquer strategy and thus provide the technological basis for the explanation facility of a principal industrial constraint programming tool, which is, for example, used in numerous configuration applications.


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.