# Counterfactual Explanations for Linear Optimization

arXiv: https://arxiv.org/abs/2405.15431 · HTML: https://mlsanity.com/paper/2405.15431/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 34 references that are in the map.
- First posted on arXiv 24 May 2024.

## Builds on (most cited first, 9 of 9)

- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [From Predictive to Prescriptive Analytics](https://mlsanity.com/paper/1402.5481/) (2014)
- [Inverse Optimization: Theory and Applications](https://mlsanity.com/paper/2109.03920/) (2021)
- [Mixed-Integer Optimization with Constraint Learning](https://mlsanity.com/paper/2111.04469/) (2021)
- [A Framework for Inherently Interpretable Optimization Models](https://mlsanity.com/paper/2208.12570/) (2022)
- [Counterfactual Explanations Using Optimization With Constraint Learning](https://mlsanity.com/paper/2209.10997/) (2022)
- [Explainable Data-Driven Optimization: From Context to Decision and Back Again](https://mlsanity.com/paper/2301.10074/) (2023)
- [Automatic Repair of Convex Optimization Problems](https://mlsanity.com/paper/2001.11010/) (2020)
- [A Framework for Data-Driven Explainability in Mathematical Optimization](https://mlsanity.com/paper/2308.08309/) (2023)

## Built on by (most cited first, 3 of 3)

- [Towards Robust Interpretable Surrogates for Optimization](https://mlsanity.com/paper/2412.01264/) (2024)
- [Coherent Local Explanations for Mathematical Optimization](https://mlsanity.com/paper/2502.04840/) (2025)
- [Decision-Value Attribution in Predict-then-Optimize Systems](https://mlsanity.com/paper/2606.29878/) (2026)

## Abstract (arXiv)

The concept of counterfactual explanations (CE) has emerged as one of the important concepts to understand the inner workings of complex AI systems. In this paper, we translate the idea of CEs to linear optimization and propose, motivate, and analyze three different types of CEs: strong, weak, and relative. While deriving strong and weak CEs appears to be computationally intractable, we show that calculating relative CEs can be done efficiently. By detecting and exploiting the hidden convex structure of the optimization problem that arises in the latter case, we show that obtaining relative CEs can be done in the same magnitude of time as solving the original linear optimization problem. This is confirmed by an extensive numerical experiment study on the NETLIB library.