Counterfactual explanations for linear optimization
本文在线性优化中引入反事实解释，提出相对、弱和强三类解释，分析其计算复杂度，并通过世界粮食计划署数据和NETLIB库实验验证相对解释可快速求解。
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.