Computing Counterfactual Explanations for Linear Optimization: A New Class of Bilevel Models and a Tailored Penalty Alternating Direction Method

Jointly with Martin Schmidt

Year: 2024

Abstract: Explainable artificial intelligence is one of the most important trends in modern machine-learning research. The idea is to explain the outcome of a model by presenting a certain change in the input of the model so that the outcome changes significantly. In this paper, we study this question for linear optimization problems as an automated decision-making tool. This leads to a new class of linear bilevel optimization problems that have more nonlinearities in their single-level reformulations compared to traditionally studied linear bilevel problems. For this class of problems, we present a tailored penalty alternating direction method and present its convergence theory that mainly ensures that we compute stationary points of the single-level reformulation. Finally, we illustrate the applicability of this method using the example of a real-world energy system model as well as by computing counterfactual explanations for a large set of linear optimization problems from the NETLIB as it has been proposed in the recent literature.

Cite as:

@misc{lefebvre2024counterfactual,
  author       = {Henri Lefebvre and Martin Schmidt},
  title        = {Computing Counterfactual Explanations for Linear Optimization: A New Class of Bilevel Models and a Tailored Penalty Alternating Direction Method},
  year         = {2024},
  note         = {Published: 2024-12-19, Updated: 2025-01-08},
  howpublished = {\url{https://optimization-online.org/?p=28803}},
  keywords     = {bilevel optimization, Counterfactual explanations, explainability, Linear Optimization, Penalty alternating direction method},
  categories   = {Energy, Nonlinear Optimization, Optimization in Data Science}
}

Open Access

Optimization Online

Open Data

We used the exact same data as the paper Counterfactual Explanations for Linear Optimization" by Jannis Kurtz, Ş. İlker Birbil, Dick den Hertog. The data is freely available on GitHub. In particular, the repository of the original paper by Kurtz and co-authors is JannisKu/CE4LOPT (original) and a forked one is hlefebvr/CE4LOPT (fork).

Open Methodology

You can find our R report for the NETLIB instances here.

Open Source

Our code will soon be available on github.
In the meantime, a general PADM implementation is available in idol.

Open Educational Resources

Some slides are available here.