Constraint Reasoning and Large Language Models Join Forces: Providing Contrastive Explanations for Real-World Optimisation-Based Applications

Roger X. Lera-Leri; Filippo Bistaffa; Athina Georgara; Juan A. Rodríguez-Aguilar

cs.AIOct 22, 2026

Constraint Reasoning and Large Language Models Join Forces: Providing Contrastive Explanations for Real-World Optimisation-Based Applications

Authors: Roger X. Lera-Leri, Filippo Bistaffa, Athina Georgara, Juan A. Rodríguez-Aguilar

Organizations: Artificial Intelligence Research Institute, IIIA-CSIC · University of Southampton

Abstract

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.

Figures & tables

Fig. 1 : Overview of our explanatory approach. Section III discusses its steps in detail.

Fig. 2 : Classes of MIP problems. While MILPs consider linear objective and constraints, MIQP considers a quadratic objective function, and MIQCP comprises problems with quadratic constraints.

Subject	Semester	Offer	Predecessors	Core
Programming Fundamentals (PF)	2 (Spring)	Both	-	Yes
Programming Techniques (PT)	4 (Spring)	Spring	PF	Yes
Object Oriented Programming (OOP)	$-$	Spring	PF	No
Operating Systems Programming (OSP)	5 (Autumn)	Autumn	PT or OOP	Yes

TABLE I : Information of the key subjects of the optimal degree plan of Example III.1 . We provide the semesters in which the subject is planned (and the season), the subject’s seasonal offer, its predecessors, and whether the subject is a core subject. If a subject is not planned, we indicate it with a

-

	Question	Query constraints	Constraint encoding ( $C_{Q}$ )
Q1.	Why is subject $u$ planned at semester $l$ ?	veto to plan $u$ at semester $l$	${x}_{u,l}=0$
Q2.	Why is subject $u$ not planned at semester $l$ ?	enforce to plan $u$ at semester $l$	${x}_{u,l}=1$
Q3.	Why is subject $u$ not planned before semester $l$ ?	enforce to plan $u$ before semester $l$	$\sum_{i=0}^{l-1}{x}_{u,i}=1$
Q4.	Why is subject $u$ not planned after semester $l$ ?	enforce to plan $u$ after $l$	$\sum_{i=l+1}^{l_{n}}{x}_{u,i}=1$
Q5.	Why is subject $u$ planned?	veto $u$	$\sum_{l\in\mathcal{L}}{x}_{u,l}=0$
Q6.	Why is subject $u$ not planned?	enforce $u$	$\sum_{l\in\mathcal{L}}{x}_{u,l}=1$

TABLE II : Set of possible user questions, query constraints and constraint encodings for the DPP formalisation.

Id	Type	Values
$q$	Query	Programming Fundamentals, Semester $4$
$c_{1}$	Completion	Programming Fundamentals
$c_{2}$	Offer	Programming Techniques not offered in Autumn
$c_{3}$	Offer	Object Oriented Prog. not offered in Autumn
$c_{4}$	Offer	Operating System Prog. not offered in Spring
$c_{5}$	Precedence	Prog. Fund. before Prog. Techniques

TABLE III :

IIS

from Example III.3 . We indicate the constraint types (in different colours) and the elements of each constraint.

Fig. 3 : Process to build a graph of reasons applied to our running example: (1) relating constraints within the IIS to yield its dual graph, and (2) labelling constraints in the dual graph to build the graph of reasons.

(i) Completion ( 4b ):	“ Subject $u$ cannot be planned more than once ”
(ii) Credits ( 4c ):	“ $d_{l}$ credits must be planned at semester $l$ ”
(iii) Offer ( 4d ):	“ Subject $u$ cannot be planned at autumn/spring semesters ”
(iv) Core ( 4e ):	“ Subject $u$ is compulsory ”
(v) Precedence ( 4f ):	“ Subject $h$ must be planned before Subject $j$ ”
(vi) Major ( 4g ):	“ Students must complete at least one major ”
(vii) Major core ( 4h ):	“ Subject $u$ is compulsory to complete major $M$ ”

TABLE IV : Natural Language Templates for each type of DPP constraint in ( 4 ). We report the Natural Language Templates for each type of RCPSP constraint in Table A3 in Appendix C .

Programming Fundamentals is not planned in semester 4 because it must be taken earlier to satisfy the prerequisite requirements of later subjects , particularly Programming Techniques and Object Oriented Programming . These subjects , in turn, need to be completed before taking Operating Systems Programming , a compulsory subject that can only be taken in the autumn . Additionally, Programming Techniques and Object-Oriented Programming cannot be scheduled in the autumn semesters, further constraining their placement. Since subjects cannot be planned more than once, Programming Fundamentals must be scheduled early enough to enable this sequence, making semester 4 too late for it.

Programming Fundamentals is scheduled in semester 2 rather than semester 4 to comply with prerequisite requirements and ensure a feasible progression through the curriculum. Since this subject must be taken before others like Programming Techniques and Object Oriented Programming , delaying it to a later semester would prevent the student from enrolling in these dependent courses on time. Additionally, university rules may restrict when certain subjects can be taken, and each subject can only be planned once, so placing Programming Fundamentals earlier allows for a coherent and complete academic path within the 6-semester limit.

TABLE V : Explanations generated using a prompt with the graph of reasons (left) and a prompt with the IIS (right) to answer the query of the running example: “ Why is Programming Fundamentals not planned at semester 4? ”. We highlight the reasons in blue .

Reasons	GoR	IIS
$r_{1}$ : PF cannot be planned more than once	✓	✓
$r_{2}$ : PT cannot be planned at autumn semesters	✓	✗
$r_{3}$ : OOP cannot be planned at autumn semesters	✓	✗
$r_{4}$ : OSP cannot be planned at spring semesters	✓	✗
$r_{5}$ : PF must be planned before PT	✓	✓
$r_{6}$ : PF must be planned before OOP	✓	✓

TABLE VI : Reasons mentioned in the explanations (shown in Table V ) generated using a prompt with the Graph of Reasons (GoR) and a prompt with the IIS.

Problem	Metric	Graph Prompt	IIS Prompt	p-value
DPP	Completeness (%)	$84\pm 3$	$64\pm 4$	$2.4\cdot 10^{-8}$
	Number of words	$82\pm 4$	$62\pm 2$	$2.1\cdot 10^{-12}$
	GFI	$20.8\pm 0.3$	$20.9\pm 0.3$	$0.86$
RCPSP	Completeness (%)	$85\pm 3$	$69\pm 4$	$2.1\cdot 10^{-7}$
	Number of words	$107\pm 4$	$85\pm 3$	$9.7\cdot 10^{-13}$
	GFI	$15.6\pm 0.2$	$16.5\pm 0.3$	$5.7\cdot 10^{-3}$

TABLE VII : Average completeness, number of words, and Gunning Fox Index (GFI) per explanation for both prompt types.

Fig. 4 : Average percentage of reasons mentioned in the explanations generated using the IIS ( red ) and using the graph of reasons ( green ). We group the explanations into three groups depending on the number of reasons: (i) small (fewer than five reasons), (ii) medium (between five and ten reasons), and (iii) large (more than ten reasons).

Fig. 5 : Boxplot of the Solving time of the MIP problem, the IIS runtime (left y axis), and the Overhead for the DPP (right y axis).

Fig. 6 : Average IIS computation time ( lines , left y-axis) and overhead ( dots , right y-axis) for different query types for the DPP .

Fig. 7 : Boxplot of the Solving time of the MIP problem, the IIS runtime (left y axis), and the Overhead for the RCPSP (right y axis).

Fig. 8 : Average IIS computation time ( lines , left y-axis) and overhead ( dots , right y-axis) for different query types for the RCPSP .

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Id	Type	Constraint Encoding
$q$	Query	$x_{PF,4}=1$
$c_{1}$	Completion	$\sum_{l=1}^{6}x_{PF,l}\leq 1$
$c_{2}$	Offer	$\sum_{l=1,3,5}x_{PT,l}=0$
$c_{3}$	Offer	$\sum_{l=1,3,5}x_{OOP,l}=0$
$c_{4}$	Offer	$\sum_{l=2,4,6}x_{OSP,l}=0$
$c_{5}$	Precedence	$x_{PF,1}\geq x_{PT,2},\sum_{l=1}^{3}x_{PF,l}\geq x_{PT,4}$

Appendix

TABLE A1 :

IIS

from Example III.3 . We indicate the constraint type (in different colours) and the corresponding mathematical encoding.

	Question	Query constraints	Constraint encoding ( $C_{Q}$ )
Q1.	Why is activity $j$ completed at time $t$ ?	veto $j$ complete at time $t$	${x}_{j,t}=0$
Q2.	Why is activity $j$ not completed at time $t$ ?	enforce $j$ complete at time $t$	${x}_{j,t}=1$
Q3.	Why is activity $j$ not completed before time $t$ ?	enforce $j$ complete before time $t$	$\sum_{t^{\prime}=EF_{j}}^{t-1}{x}_{j,t^{\prime}}=1$
Q4.	Why is activity $j$ not completed after time $t$ ?	enforce $j$ to complete after $t$	$\sum_{t^{\prime}=t+1}^{LF_{j}}{x}_{j,t^{\prime}}=1$
Q5.	Why is the group of activities $A$ completed at $t$ ?	veto to complete $j\in A$ at time $t$	$\sum_{j\in A}{x}_{j,t}<\|A\|$
Q6.	Why is the group of activities $A$ not completed at $t$ ?	enforce to complete all of them at time $t$	$\sum_{j\in A}{x}_{j,t}=\|A\|$

Appendix

TABLE A2 : Set of possible user questions, query constraints and constraint encodings for the RCPSP formalisation.

(i) Completion :	“ Activity j must be completed ”
(ii) Precedence :	“ Act. h must be completed before Act. j starts ”
(iii) Resource :	“ Res. r is scarce at time $t$ due to Acts. $i,\dots,j$ ”

Appendix

TABLE A3 : Templates for each type of RCPSP constraints.

The bachelor’s degree planning problem is the problem of finding a plan of university subjects that respects some precedence and university restrictions while maximising the skills learnt. Specifically, the goal is to acquire the required level for the student’s desired job role through the course subjects. In this context, provide an explanation to answer the following question about the solution to the 6-semester bachelor’s degree planning problem. To do so, use the reasons below, which are related to the bachelor’s degree restrictions. Moreover, these reasons are connected to one another like nodes in a graph. Use the reasons and their connections to write the explanation.

Partial Solution:
Subject	Semester	Offer	Predecessors	Core
Prog. Fund.	2 (Spring)	Both	-	Yes
Prog. Tech.	4 (Spring)	Spring	PF	Yes
Obj. Or. Prog.	$-$	Spring	PF	No

Appendix

TABLE A4 : Prompt using the Graph of Reasons to answer the query of the running example.

The bachelor’s degree planning problem is the problem of finding a plan of university subjects that respects some precedence and university restrictions while maximising the skills learnt. Specifically, the goal is to acquire the required level for the student’s desired job role through the course subjects. In this context, provide an explanation to answer the following question about the solution to the 6-semester bachelor’s degree planning problem. To do so, use the reasons below, which are related to the bachelor’s degree restrictions.

Partial Solution:
Subject	Semester	Offer	Predecessors	Core
Prog. Fund.	2 (Spring)	Both	-	Yes
Prog. Tech.	4 (Spring)	Spring	PF	Yes
Obj. Or. Prog.	$-$	Spring	PF	No

Appendix

TABLE A5 : Prompt using the IIS (with their constraints translated) to answer the query of the running example.

Constraint-Guided Reasoning in Language Models

See all 23 papers

ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization
Feb 25, 2026Joseph Tso, Preston Schmittou, Quan Huynh +1Constraint-Guided Reasoning in Language Models Constrained Optimization
Haladir Research Team
Reliable Reasoning with Large Language Models via Preference-Based Maximum Satisfiability
May 28, 2026Pedro Orvalho, Marta Kwiatkowska, Guillem Alenyà +1Large Language Model-Guided Optimization LLM-Based Program Synthesis
Artificial Intelligence Research Institute (IIIA) Consejo Superior de Investigaciones Científicas (CSIC) Barcelona, Catalonia, Spain · Department of Computer Science University of Oxford Oxford, UK · Institut de Robòtica i Informàtica Industrial (IRI-CSIC-UPC) Barcelona, Catalonia, Spain
COOPA: A Modular LLM Agent Architecture for Operations Research Problems
Jun 25, 2026Chuanhao Li, Xiaoan Xu, Dirk Bergemann +3Multi-Agent LLM Systems Multi-Agent Orchestration
1Tsinghua University · 2Duke University · 3Yale University

Feb 25, 2026J/K move · Enter open · S save

ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization

Joseph Tso, Preston Schmittou, Quan Huynh, Jibran Hutchins

Haladir Research Team

Constraint-Guided Reasoning in Language Models Constrained Optimization LLM Reasoning Operations Research

Open paper AskPDF arXiv

Large language models are increasingly applied to operational decision-making where the underlying structure is constrained optimization. Existing benchmarks evaluate whether LLMs can formulate optimization problems as solver code, but leave open a complementary question. Can LLMs directly produce correct solutions to fully specified constrained optimization problems without access to a solver? We introduce ConstraintBench, a benchmark for evaluating LLMs on direct constrained optimization across 10 operations research domains, with all ground-truth solutions verified by the Gurobi solver. Each task presents a natural-language scenario with entities, constraints, and an optimization objective; the model must return a structured solution that a deterministic verifier checks against every constraint and the solver-proven optimum. We evaluate six frontier models on 200 tasks and find that feasibility, not optimality, is the primary bottleneck. The best model achieves only 65.0% feasibility, yet feasible solutions average 89 to 96% of the Gurobi-optimal objective. No model exceeds 30.5% on joint feasibility and optimality within 0.1% of the solver reference. Per-domain analysis shows large variation in difficulty, with average feasibility spanning from 85.0% in the facility location domain to 0.8% in the crew assignment domain. Further, systematic failure modes include duration constraint misunderstanding, entity hallucination, and a feasibility-optimality decoupling in facility location and vehicle routing where models achieve high feasibility but 0% optimality. ConstraintBench and all evaluation infrastructure will be publicly released.

Abstract

Constraint-Guided Reasoning in Language Models

Explore similar work

ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization

Reliable Reasoning with Large Language Models via Preference-Based Maximum Satisfiability

COOPA: A Modular LLM Agent Architecture for Operations Research Problems