Counterfactual explanations for linear optimization

In recent years, the concept of counterfactual explanations (CE) has become increasingly important in understanding the inner workings of complex AI systems. In this paper, we introduce the idea of CEs in the context of linear optimization and propose, explain, and analyze three different classes of CEs: relative, weak, and strong. We discuss in which situation each type of CE is needed and examine the structure of the optimization problems that arise from considering them. By detecting and leveraging the underlying convex structure of the relative CE problem, we demonstrate that computing the relative CEs takes the same order of time as solving the original problems. We also address the computational challenges associated with weak and strong CE problems. To illustrate our findings, we present a case study with data sourced from the World Food Programme in which we calculate each type of CE. Finally, we conduct comprehensive numerical experiments using the NETLIB library to demonstrate that relative CE problems can be solved as quickly as solving the original linear optimization problem.