# Exploiting Constraint Reasoning to Build Graphical Explanations for Mixed-Integer Linear Programming

arXiv: https://arxiv.org/abs/2507.13007 · HTML: https://mlsanity.com/paper/2507.13007/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 48 references that are in the map.
- First posted on arXiv 17 Jul 2025.

## Builds on (most cited first, 12 of 12)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI](https://mlsanity.com/paper/1910.10045/) (2019)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Towards Explainable Artificial Intelligence](https://mlsanity.com/paper/1909.12072/) (2019)
- [Rethinking Explainability as a Dialogue: A Practitioner's Perspective](https://mlsanity.com/paper/2202.01875/) (2022)
- [A framework for step-wise explaining how to solve constraint satisfaction problems](https://mlsanity.com/paper/2006.06343/) (2020)
- [Explaining Preference-driven Schedules: the EXPRES Framework](https://mlsanity.com/paper/2203.08895/) (2022)
- [Efficiently Explaining CSPs with Unsatisfiable Subset Optimization (extended algorithms and examples)](https://mlsanity.com/paper/2303.11712/) (2023)
- [Causal Explanations of Structural Causal Models](https://mlsanity.com/paper/2110.02395/) (2021)
- [Contrastive Explanations of Centralized Multi-agent Optimization Solutions](https://mlsanity.com/paper/2308.05984/) (2023)
- [Synergistic Team Composition: A Computational Approach to Foster Diversity in Teams](https://mlsanity.com/paper/1909.11994/) (2019)
- [An attention model for the formation of collectives in real-world domains](https://mlsanity.com/paper/2205.00215/) (2022)

## Abstract (arXiv)

Following the recent push for trustworthy AI, there has been an increasing interest in developing contrastive explanation techniques for optimisation, especially concerning the solution of specific decision-making processes formalised as MILPs. Along these lines, we propose X-MILP, a domain-agnostic approach for building contrastive explanations for MILPs based on constraint reasoning techniques. First, we show how to encode the queries a user makes about the solution of an MILP problem as additional constraints. Then, we determine the reasons that constitute the answer to the user's query by computing the Irreducible Infeasible Subsystem (IIS) of the newly obtained set of constraints. Finally, we represent our explanation as a "graph of reasons" constructed from the IIS, which helps the user understand the structure among the reasons that answer their query. We test our method on instances of well-known optimisation problems to evaluate the empirical hardness of computing explanations.