There has been a recent push to make machine learning models more interpretable so that their performance can be trusted. Although successful, this push has primarily focused on deep learning methods, while simpler optimization methods have been essentially ignored. Consider linear programs (LP), a working horse of sciences. Even if LPs can be considered whitebox or clearbox models, they are not easy to understand in terms of relationships between inputs and outputs, contrary to common belief. As a linear program solver only provides the optimal solution to an optimization problem, further explanations are often helpful. We extend the attribution methods for explaining neural networks to linear programs, thereby taking the first step towards what might be called explainable optimization. These attribution methods explain the model by providing relevance scores for the model inputs to show the influence of each input on the output. Alongside using classical gradient-based attribution methods, we also propose a way to adapt perturbation-based attribution methods to LPs. Our evaluations of several different linear and integer problems show that attribution methods can generate helpful explanations for these models. In particular, we demonstrate that explanations can generate interesting insights into large, real-world linear programs.

Linear Programs (LPs) are one of the major building blocks of AI and have championed recent strides in differentiable optimizers for learning systems. While there exist efficient solvers for even high-dimensional LPs, explaining their solutions has not received much attention yet, as explainable artificial intelligence (XAI) has mostly focused on deep learning models. LPs are mostly considered whitebox and thus assumed simple to explain but we argue that they are not easy to understand in terms of relationships between inputs and outputs. To mitigate this rather non-explainability of LPs we show how to adapt attribution methods by encoding LPs in a neural fashion. The encoding functions consider aspects such as feasibility of the decision space, the cost attached to each input and the distance to special points of interest. Using a variety of LPs, including a very large-scale LP with 10k dimensions, we demonstrate the usefulness of explanation methods using our neural LP encodings, though, the attribution methods Saliency and LIME are indistinguishable for low perturbation levels. In essence, we demonstrate that LPs can and should be explained which can be achieved by representing an LP as a neural network.