Jannis Kurtz: Counterfactual Explanations for Linear Optimization 9 January 2025 16:00 - 17:00

In recent years, there has been a rising demand for transparent and explainable machine learning (ML) models. A large stream of works focuses on algorithmic methods to derive so called counterfactual explanations (CE). Although significant progress has been made in generating CEs for ML models, this topic has received minimal attention in the Operations Research (OR) community. However, algorithmic decisions in OR are made by complex algorithms which cannot be considered to be explainable or transparent. In this work we argue that there exist many OR applications where counterfactual explanations are needed and useful. We translate the concept of CEs into the world of linear optimization problems and define three different classes of CEs: strong, weak and relative counterfactual explanations. For all three types we derive problem formulations and analyze the structure. We show that the weak and strong CE formulations have some undesirable properties while relative CEs can be derived by solving a tractable convex optimization problem. We test all concepts on a real-world diet problem and we show that relative CEs can be calculated efficiently on NETLIB instances.