Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

7-2026

Abstract

Stepwise explanations are an important tool for interpreting constraint programs. Existing methods rely heavily on repeated minimal unsatisfiable subsets (MUS) extraction or intensive SAT-based propagation, which are computationally prohibitive for large-scale problems with complex constraints. We propose a novel framework leveraging Multi-Valued Decision Diagrams (MDDs) to overcome these bottlenecks. By decomposing CSPs into smaller, graph-based subproblems compactly represented as MDDs, we enable highly efficient constraint propagation through network-flow reformulation. To further enhance efficiency, we propose a Divide-and-Conquer approach to improve the search for minimal explanation steps. Furthermore, we utilize the MDD’s network-flow structure to generate nested explanations that break down complex derivation steps into granular, arc-level details, revealing specifically how variable-value assignments become infeasible. In this way, our approach equips the explainer agent with a voice that provides more intuitive and granular stepwise explanations. Evaluated on Graph Coloring and Nurse Rostering benchmarks, our framework significantly reduces explanation generation time while maintaining interpretability and conciseness compared to state-of-the-art methods.

Keywords

overconstraint, explanation, propagation, multi-valued decision diagrams

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Sustainability

Publication

Proceedings of the 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026), Lisbon, Portugal, July 20-23

Volume

379

First Page

1

Last Page

24

Identifier

10.4230/LIPIcs.CP.2026.44

Publisher

Schloss Dagstuhl

City or Country

Wadern, Germany

Additional URL

https://doi.org/10.4230/LIPIcs.CP.2026.44

Download

Share

COinS