Constraint Reasoning and Large Language Models Join Forces: Providing Contrastive Explanations for Real-World Optimisation-Based Applications
Optimisation-based decision support systems recommend schedules or plans by solving mixed-integer programs, but end users often ask "why not X?" contrastive questions that are hard to answer reliably with pure LLMs. This paper proposes LLMxMIP, a pipeline that extracts irreducible infeasible subsystems from a constraint model, organises them into a structured graph of reasons, and prompts an LLM to generate a textual explanation. The work matters because it marries rigorous constraint reasoning with natural language generation to address a real oversight requirement in automated decision-making.
The paper presents a well-motivated, architecturally clean methodology for contrastive explainability in MIP-based DSS. The core idea of distilling an IIS into a dual graph with natural language templates before LLM generation is conceptually sound and empirically beneficial. However, the evaluation leans heavily on automated completeness and readability metrics without human user judgments, and the need for hand-crafted templates per constraint type limits the advertised domain independence. It is a solid step forward for the field, but its practical impact awaits validation with end users.
The hybrid pipeline is technically coherent: IIS extraction guarantees that the causal core of infeasibility is identified, while the graph-of-reasons structure demonstrably improves LLM outputs. The empirical results on two distinct scheduling domains — a real-world degree planning problem and standard RCPSP benchmarks — show consistent gains in explanation completeness, and the runtime analysis is pragmatic, showing that explanation overheads are manageable and often much lower than solving the original MIP.
The strongest limitation is the absence of any human evaluation; the authors acknowledge this as future work, yet claims about explanation quality rest entirely on automated metrics. Completeness is measured by string-matching reasons from the IIS against LLM outputs, which is a proxy that does not verify factual correctness or human interpretability, and the Gunning Fog Index is a coarse readability signal. Additionally, the approach requires domain experts to craft natural language templates for every constraint type, so portability to new domains is not as automatic as suggested. The LLM experiments use only GPT-4o with a zero-shot prompt, leaving open whether the gains generalise across models or prompting strategies.
The evidence supports the narrow claim that structured prompting with a graph of reasons yields more complete explanations than unstructured IIS lists for GPT-4o. Section IV-B reports average completeness of 84% versus 64% for DPP and 85% versus 69% for RCPSP, with statistically significant p-values. However, the comparison baseline is minimal — just an unordered list of templated constraints — and the paper does not benchmark against other optimisation explainability methods such as what-if analysis or MUS-based approaches from the SAT literature. The Related Work section discusses these alternatives fairly but does not empirically pit LLMxMIP against them.
The paper benefits from strong reproducibility artefacts: CPLEX is used for solving and IIS computation, the code and data are publicly available on GitHub and Zenodo, and the prompt designs are documented in Appendix D. That said, reproducing the LLM outputs exactly is difficult because the authors do not report hyperparameters such as temperature or top-p, and GPT-4o is a closed, potentially changing model. The constraint-to-template mappings for RCPSP and DPP are provided, which helps, but replicating the approach on a new domain still requires substantial manual engineering to build the template library.
We focus on optimisation-based Decision Support Systems in real-world applications. In this context, we aim to provide contrastive explanations that answer users' questions about recommendations based on the solution of an optimisation problem, specifically a Mixed-Integer Program (MIP). Addressing this endeavour is crucial to ensure human oversight of the decisions implemented, as required by international guidelines on trustworthy and responsible automated decision-making systems. We propose a novel methodology that combines constraint reasoning techniques and Large Language Models (LLMs) to generate contrastive explanations for optimisation problems encoded as MIPs. Although LLMs have shown impressive capabilities in Natural Language processing, they can produce incorrect answers due to reasoning limitations. To overcome these limitations, we leverage constraint reasoning techniques to distil the information necessary to produce an explanation, which is then passed as input to an LLM as the so-called graph of reasons. Such a graph captures the semantics and the relationships among constraints of the optimisation problem. Results on real-world scheduling domains show that incorporating constraint reasoning improves explanations generated by the LLM. In particular, using the graph of reasons enables the LLM to produce natural-language explanations that include more relevant reasons while reducing errors compared to explanations generated without this structure.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.