%AErwig, Martin%AKumar, Prashant%BJournal Name: Journal of Computer Languages; Journal Volume: 79; Journal Issue: C
%D2024%IElsevier
%JJournal Name: Journal of Computer Languages; Journal Volume: 79; Journal Issue: C
%KContrastive explanation, Explanation simplification
%MOSTI ID: 10527161
%PMedium: X
%TExplanations for combinatorial optimization problems
%XWe introduce a representation for generating explanations for the outcomes of combinatorial optimization algorithms. The two key ideas are (A) to maintain fine-grained representations of the values manipulated by these algorithms and (B) to derive explanations from these representations through merge, filter, and aggregation operations. An explanation in our model presents essentially a high-level comparison of the solution to a problem with a hypothesized alternative, illuminating why the solution is better than the alternative. Our value representation results in explanations smaller than other dynamic program representations, such as traces. Based on a measure for the conciseness of explanations we demonstrate through a number of experiments that the explanations produced by our approach are small and scale well with problem size across a number of different applications.
%0Journal Article