Efficiently Explaining CSPs with Unsatisfiable Subset Optimization

Emilio Gamba, Bart Bogaerts, Tias Guns

TL;DR

This paper introduces a new method for efficiently generating human-understandable explanations of Constraint Satisfaction Problem (CSP) solutions. By optimizing the search for "Optimal Constrained Unsatisfiable Subsets" (OCUS), the authors significantly speed up the explanation process and improve the quality of explanations compared to previous MUS-based approaches.

What Problem Does This Paper Address?

Explaining how a constraint solver arrives at a solution is crucial for debugging, understanding, and teaching. Existing methods often rely on finding Minimal Unsatisfiable Subsets (MUSs) of a derived unsatisfiable formula. However, these MUS extraction algorithms don't guarantee optimal explanations (with respect to a given cost function that approximates human understandability) and can be computationally very expensive, taking hours even for simple puzzles. This paper addresses these two main weaknesses: the lack of optimality guarantees and the poor performance of MUS-based explanation generation.

Methods

The core contribution is the introduction of the Optimal Constrained Unsatisfiable Subset (OCUS) problem. This generalizes the concept of MUS to find an unsatisfiable subset that is optimal with respect to a given cost function and satisfies specific constraints. The authors propose an algorithm for computing OCUSs based on the hitting set duality, leveraging mixed-integer programming (MIP) solvers.

Key algorithmic contributions include:

  • OCUS Algorithm: A general algorithm for computing OCUSs by iteratively finding hitting sets and correction subsets.
  • Explain-One-Step-OCUS: Adapting the OCUS computation for the specific constraint of finding an explanation step that involves "exactly one" new literal.
  • Bounded OCUS: Using the cost of the best explanation found so far as an upper bound to prune the search space for subsequent OCUS computations.
  • Interleaving OCUS Calls (OCUS_Split): A strategy that iteratively selects the most promising literal to explain and performs one hitting set iteration at a time, rather than fully computing an OCUS for each literal.
  • Incremental OCUS: Reusing information (specifically, the collection of sets-to-hit) across multiple OCUS calls within the explanation sequence generation process, significantly speeding up computation by keeping the MIP solver "warm."
  • Advanced Correction Subset Enumeration: Developing strategies like "Multi-SubsetMax-SAT" to efficiently find multiple, ideally p-disjoint, correction subsets, which in turn reduces the number of sets-to-hit for the solver.

Datasets

The paper evaluates their algorithms on a variety of benchmark datasets, including:

  • Generated Sudoku puzzles of increasing difficulty.
  • Logic Grid puzzles from Bogaerts et al. (2021).
  • Instances from Espasa et al. (2021).

Key Insights and Ideas

  • OCUS as a Generalization: The OCUS framework provides a more principled way to find optimal explanations by directly incorporating cost functions and specific constraints, moving beyond the heuristic nature of MUS-based approaches.
  • Hitting Set Duality is Key: The paper effectively leverages the well-established hitting set duality between Minimal Correction Subsets (MCSs) and Minimal Unsatisfiable Subsets (MUSs) to build their OCUS algorithms.
  • Incrementality Pays Off: Reusing computed information (especially the sets-to-hit in MIP solvers) across explanation steps dramatically reduces computation time, making interactive explanations feasible.
  • "Grow" Strategy Matters: The method used to grow satisfiable subsets into larger ones (e.g., using SAT or MaxSAT) significantly impacts the efficiency of finding correction subsets and, consequently, the overall explanation time.
  • Trade-offs in Correction Subset Enumeration: There's a clear trade-off between the efficiency of finding correction subsets and the quality of the resulting satisfiable subset. Advanced methods like Multi-SubsetMax-SAT effectively balance this.

Key Results

  • Explanation Quality: The OCUS-based approach produces significantly better explanations (lower cost) than MUS-based methods, often finding much cheaper explanations that MUS-based methods miss.
  • Performance Improvement:
    • The proposed OCUS algorithms, especially with incrementality and the OCUS_Split strategy, are substantially faster than MUS-based approaches.
  • For example, OCUS_Split+Incr. combined with Multi-SubsetMax-SAT is highlighted as the best configuration, achieving significant speedups.
  • Incrementality alone reduces the number of sets-to-hit by orders of magnitude (e.g., from 6245 to 405 for OCUS).
  • Interactive explanations can be generated in near real-time (less than a second) using OCUS_Split.
  • Logic Grid Puzzles: Full explanations for logic grid puzzles, which previously took hours, can now be generated in minutes using their optimized OCUS approach.

Limitations and Future Work

  • Non-linear Cost Functions: The current MIP implementation of OCUS has limitations with non-linear cost functions, which might not fully capture the complexity of "good" explanations.
  • Interpretability Metrics: The question of which interpretability metric is most suitable for characterizing understandable explanations remains open.
  • Generalization to Other Problems: The authors are interested in exploring the application of OCUS to other domains like configuration and machine learning, and its relation to the more general problem of QMaxSAT.
  • Parallelization: For interactive tutoring systems, distributing computation across multiple cores to further speed up explanation generation is a promising future direction.
  • Interactive Settings: Investigating other methods for enumerating correction subsets that are better suited for interactive settings is also suggested.

Summary updated

BibTeX
@inproceedings{gamba2021efficiently,
  author = {Emilio Gamba and Bart Bogaerts and Tias Guns},
  title = {{Efficiently Explaining CSPs with Unsatisfiable Subset Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/191},
}
Figure