License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.11
URN: urn:nbn:de:0030-drops-190489
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19048/
Bleukx, Ignace ;
Devriendt, Jo ;
Gamba, Emilio ;
Bogaerts, Bart ;
Guns, Tias
Simplifying Step-Wise Explanation Sequences
Abstract
Explaining constraint programs is useful for debugging an unsatisfiable program, to understand why a given solution is optimal, or to understand how to find a unique solution. A recently proposed framework for explaining constraint programs works well to explain the unique solution to a problem step by step. It can also be used to step-wise explain why a model is unsatisfiable, but this may create redundant steps and introduce superfluous information into the explanation sequence. This paper proposes methods to simplify a (step-wise) explanation sequence, to generate simple steps that together form a short, interpretable sequence. We propose an algorithm to greedily construct an initial sequence and two filtering algorithms that eliminate redundant steps and unnecessarily complex parts of explanation sequences. Experiments on diverse benchmark instances show that our techniques can significantly simplify step-wise explanation sequences.
BibTeX - Entry
@InProceedings{bleukx_et_al:LIPIcs.CP.2023.11,
author = {Bleukx, Ignace and Devriendt, Jo and Gamba, Emilio and Bogaerts, Bart and Guns, Tias},
title = {{Simplifying Step-Wise Explanation Sequences}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {11:1--11:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-300-3},
ISSN = {1868-8969},
year = {2023},
volume = {280},
editor = {Yap, Roland H. C.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19048},
URN = {urn:nbn:de:0030-drops-190489},
doi = {10.4230/LIPIcs.CP.2023.11},
annote = {Keywords: explanation, deduction, constraint programming, propagation}
}
