Decision-Tree Surrogates for Weak Counterfactual Explanations in Integer Optimization
Abstract
The concept of counterfactual explanations (CEs) has recently gained increasing attention for deriving explanations of mathematical optimization problems. For a given problem, a counterfactual is an ideally minimal change in the mutable problem parameters such that an optimal solution of the changed problem exists fulfilling some desired criterion. It was shown that so-called weak CEs can be calculated by solving a computationally demanding bilevel optimization problem, which is Σ2p-complete if decision variables and mutable parameters are restricted to integers. Hence, the known exact solution methods are expected to fail on practically relevant problem sizes. In this work we derive a fast heuristic algorithm by approximating the feasible region of the CE problem with a decision tree for which CEs can be calculated more quickly. To this end we analyze the mathematical structure of the feasible region and develop a hand-crafted decision tree which applies splits imitating this structure. Additionally, we develop several techniques to increase the performance of our method. The practicability of our methods is supported by computational experiments on the knapsack problem and the facility location problem.
Related
- An integrated explainable AI framework with counterfactual optimization for decision support
- Are Good Generators Good Decision-Makers? Policy Learning for General Interventions via Retargeted Counterfactual Generation
- A Globally Convergent Newton Method for Nonsmooth Optimization in the absence of Smooth Surrogates
- Improving the Optimization Landscape of Matrix Completion with ε-close Surrogates
- On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization
BibTeX
@misc{goerigk2026decisiontree,
title = {{Decision-Tree Surrogates for Weak Counterfactual Explanations in Integer Optimization}},
author = {Marc Goerigk and Jannis Kurtz and Sebastian Merten},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05887},
eprint = {2610.05887},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05887},
}
RIS
TY - UNPB
TI - Decision-Tree Surrogates for Weak Counterfactual Explanations in Integer Optimization
AU - Marc Goerigk
AU - Jannis Kurtz
AU - Sebastian Merten
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.05887
UR - https://arxiv.org/abs/2610.05887
AB - The concept of counterfactual explanations (CEs) has recently gained increasing attention for deriving explanations of mathematical optimization problems. For a given problem, a counterfactual is an ideally minimal change in the mutable problem parameters such that an optimal solution of the changed problem exists fulfilling some desired criterion. It was shown that so-called weak CEs can be calculated by solving a computationally demanding bilevel optimization problem, which is Σ_2^p-complete if decision variables and mutable parameters are restricted to integers. Hence, the known exact solution methods are expected to fail on practically relevant problem sizes. In this work we derive a fast heuristic algorithm by approximating the feasible region of the CE problem with a decision tree for which CEs can be calculated more quickly. To this end we analyze the mathematical structure of the feasible region and develop a hand-crafted decision tree which applies splits imitating this structure. Additionally, we develop several techniques to increase the performance of our method. The practicability of our methods is supported by computational experiments on the knapsack problem and the facility location problem.
ER -