  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.
