Counterfactual Explanations for Linear Optimization
This provides a method for explaining linear optimization models, which is incremental as it adapts an existing concept to a new domain.
The paper tackles the problem of generating counterfactual explanations for linear optimization, showing that while strong and weak types are computationally intractable, relative counterfactual explanations can be computed efficiently, with experiments on the NETLIB library confirming they take similar time as solving the original problem.
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.