EURO 2025 Leeds
Abstract Submission

497. Counterfactual Explanations for Binary Knapsack Problems

Invited abstract in session WB-48: New Approaches in Explainable Optimization, stream Transparent and Fair Decision Making with Mathematical Optimization.

Wednesday, 10:30-12:00
Room: Parkinson B09

Authors (first author is the speaker)

1. Felix Engelhardt
Research and Teaching Area Combinatorial Optimization, RWTH Aachen University
2. Jannis Kurtz
Amsterdam Business School, University of Amsterdam
3. Ilker Birbil
Business Analytics, Amsterdam University
4. Ted Ralphs
Industrial and Systems Engineering, Lehigh University
5. Dick den Hertog
University of Amsterdam

Abstract

Counterfactual explanations (CE) are predominantly used in machine learning. Kurtz, Birbil und den Hertog (2024) extended this notion to linear programming. In this talk, we present the first results on CEs for integer linear programming (ILP).

We show that the notions of weak, strong and relative CEs translate from linear to ILP. Relative CEs for ILP are as hard to compute as the original problem, as long as no special matrix structure (e.g. totally unimodular) is destroyed by the modification.

Weak and strong CEs are generally harder to solve, depending on the mutable parameter space used to compute CEs. For only objective variations, computing CEs is closely linked to existing work on inverse optimization. For, right-hand-side only variations, it suffices to solve a pseudo-polynomial number of instances of the original problem.

Thus, this talk focuses on the most relevant and challenging case, i.e. mutable matrix parameters A. Here, we can show that computing a CE is at least S2P-hard in terms of theoretical complexity, and thus no polynomial time ILP formulation for the CE problem is likely to exist. We then present an enumeration algorithm to solve different types of Knapsack instances. This algorithm is validated through a computational study, results of which are presented as well. Finally, we outline how this method can be extended to problems with multiple constraints or negative parameters.

Keywords

Status: accepted

Back to the list of papers