Mixed-Integer Programming for Exact Counterfactual Explanations

34 concepts24 papers1 proposal

When a machine learning model denies a loan application or flags a transaction as fraudulent, the immediate question is: Why? More importantly, the user asks: What would I need to change to get a different result? This is the problem of counterfactual explanations—finding the minimal modification to an input that flips the model's prediction.

While early methods relied on gradient descent or heuristic searches, a growing body of research suggests that the most robust way to find these explanations is to treat the search as a formal optimization problem. By using Mixed-Integer Programming (MIP), researchers can find "exact" solutions that are mathematically guaranteed to be the closest, most feasible, and most actionable paths to a desired outcome.

To find a counterfactual, one might naturally try to follow the gradient of a model's output toward the desired class. However, this approach struggles with two fundamental realities of real-world data:

  1. Discrete Features: Many inputs are categorical (e.g., "Education Level" or "Marital Status"). Gradients cannot easily navigate these discrete jumps.
  2. Non-Differentiable Models: Popular models like Random Forests or Gradient Boosted Trees do not have smooth gradients to follow.

Kanamori et al. argue that gradient-based methods often fail to navigate the discrete decision boundaries of tree-based ensembles. Similarly, Artelt et al. note that while contrastive explanations are intuitive for humans, computing them for complex models has traditionally lacked mathematical guarantees.

Mapping Logic to Linear Constraints

The core insight of this research direction is that the internal logic of many AI models can be translated into a set of linear inequalities. Once a model is represented this way, the search for a counterfactual becomes a Mixed-Integer Linear Programming (MILP) problem.

For example, Karimi et al. demonstrated that neural networks using ReLU activations can be encoded into MIP frameworks. This allows for the generation of "provably nearest" counterfactuals with 100% coverage, bridging the gap between slow logic solvers and fast but inexact gradient methods.

In the realm of tree ensembles, Parmentier et al. showed that by reducing the number of variables in the optimization model, one can find globally optimal explanations for large forests in seconds. This replaces unreliable heuristics with an exact search that identifies the absolute minimum-cost path to a new classification.

Beyond Distance: Feasibility and Actionability

A counterfactual is useless if it suggests an impossible change, such as "reduce your age by five years." MIP is particularly powerful here because it allows for the enforcement of hard constraints.

Russell introduced a framework using a "mixed polytope" constraint to ensure that explanations are not just mathematically close, but physically possible and coherent. This prevents the system from suggesting nonsensical states.

Furthermore, the authors of Algorithmic Recourse: from Counterfactual Explanations to Interventions distinguish between mutable features (which can change as a side effect) and actionable features (which a user can directly control). By framing recourse as a set of minimal causal interventions, Karimi et al. ensure that the suggested actions respect the way the world actually works.

A Unified Framework for Reasoning

This optimization-centric approach extends beyond simple "what-if" questions into the broader field of abductive reasoning—finding the best explanation for a set of observations.

The roots of this idea go back to Charniak et al., who transformed story-understanding tasks into 0-1 linear programming problems to achieve significant speedups. More recently, Inoue et al. applied Integer Linear Programming (ILP) to weighted abduction, allowing systems to reason over hundreds of thousands of logical axioms from databases like WordNet in seconds.

Whether the task is coreference resolution in natural language (Inoue et al.), explaining path planning in robotics (Brandão et al.), or auditing fairness in group decisions (Fragkathoulas et al.), the underlying mechanism remains the same:

  1. Encode the model's logic and the data's constraints into linear inequalities.
  2. Define a cost function (e.g., distance, effort, or sparsity).
  3. Solve using high-performance mathematical solvers to find the provably optimal explanation.

By moving from heuristic search to exact optimization, these frameworks provide users with explanations that are not just "likely," but mathematically certain and practically actionable.

Key Foundational Work

Dynamic MAP Calculations for Abduction (1992) — contributed 1 concept elements to this direction.
Log-Linear Description Logics (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_exact_counterfactual_optimization_6ddd27e9,
  title = {exact counterfactual optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/exact-counterfactual-optimization/rdr_6ddd27e995784323a2474b6a1a6d9f2b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_exact_counterfactual_optimization_6ddd27e9_v1,
  title = {exact counterfactual optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/exact-counterfactual-optimization/rdr_6ddd27e995784323a2474b6a1a6d9f2b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake