Cost-Minimal Parameter Correction Subsets for Unsatisfiable Constraint Problems
摘要
Decision support systems developed for real-world applications often rely on solving complex combinatorial problems using carefully crafted constraint models. However, users of such systems may input data that leads to a problem without any solution, rendering it unsatisfiable. The responsibility of understanding and correctly modifying the data generally falls on the user. Previous research on unsatisfiability mainly focused on reporting subsets of problematic constraints, which requires a good understanding of the underlying model. We introduce the concept of Cost-Minimal Parameter Correction Subset (CMPCS) as a subset of data parameters and their correction to make an instance satisfiable at a minimal cost. We propose a problem-independent approach, called CMPCS-Finder, which aims at reporting a CMPCS given an unsatisfiable instance. We empirically evaluate this approach on existing combinatorial benchmark problems and demonstrate that, in most cases, it successfully identifies the changes in the data that initially caused the instances to be unsatisfiable.