PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.31119v1cs.AI

TL;DR

Optimization-based DSS need contrastive explanations that help users understand recommendations, but LLMs can struggle with reasoning across constraints. LLMxMIP uses constraint reasoning to build a graph of reasons for an LLM, and its evaluation reports improved explanation quality across two scheduling problems.

  • Problem

    Explaining optimization-based DSS recommendations matters for human oversight, while LLMs can struggle to reason reliably across the interdependent constraints behind those recommendations.

    Source: §I · p. 1

  • Method

    LLMxMIP uses constraint reasoning to identify conflicts and organize their relationships and semantic interpretations in a graph of reasons that an LLM uses to generate textual explanations.

    Source: §I · p. 2

  • Results

    Across a real-world DPP instance and realistic RCPSP benchmarks, graph-of-reasons input significantly improves explanation completeness and readability, and explanations are generated in real time in most cases.

    Source: §I · p. 2, §VI · p. 15

  • Takeaways & Limitations

    The reported evaluation demonstrates LLMxMIP on two distinct real-world scheduling settings: degree planning and project scheduling.

    Source: §VI · p. 15

    Whether intended users find the explanations useful remains to be evaluated in a planned study with bachelor’s degree students.

    Source: §VI · p. 15

Abstract

from arXiv · show

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.

I. INTRODUCTION

Optimization-based DSS need to explain recommendations to support human oversight, but LLMs can struggle to reason over interdependent constraints. LLMxMIP combines constraint reasoning with an LLM to generate contrastive explanations, and the paper reports improved explanation quality across two scheduling domains.

I. INTRODUCTION

  • The RCPSP minimizes project makespan, whereas the DPP maximizes user preferences linked to desired jobs, providing complementary scheduling use cases.Source: §I · p. 1
  • Optimization-based DSS recommend schedules or degree plans, but explaining those recommendations has received less attention than explaining decisions from machine-learning systems.The paper frames explanation as important for the human oversight required by international AI regulations.Source: §I · p. 1
  • Users seek contrastive explanations that explain why a recommendation was made rather than an alternative, while LLMs may produce incorrect or vague explanations of constraint-heavy outcomes.Examples include wrongly calling a user-proposed alternative infeasible or failing to identify which constraints prevent it.Source: §I · pp. 1–2
  • LLMxMIP converts a user query into constraints, reformulates the optimization problem as a CSP, extracts an IIS, structures its constraint relationships as a graph of reasons, and prompts an LLM to generate text.The IIS is the minimal subset of constraints that makes the query-compliant CSP infeasible.Source: §I · p. 2
  • Across the DPP and RCPSP, graph-of-reasons input significantly improves explanation completeness and readability, while LLMxMIP computes explanations faster than solving the optimization problems in most cases.The evaluation uses a real-world degree-planning instance and realistic RCPSP benchmark instances.Source: §I · p. 2

A. Mathematical Optimisation

B. Optimisation Problems Domains

The RCPSP formalisation schedules activities subject to precedence and renewable-resource constraints while minimising the project’s duration. It uses a single-mode variant with bounded activity time windows.

1) The Resource-Constrained Project Scheduling Problem:

  • The formalisation can be extended to Mixed-Integer Convex Programming by switching to the MOSEK solver.MOSEK is described as capable of solving that family of optimisation problems.Source: 1) The Resource-Constrained Project… · p. 3
  • The RCPSP seeks a feasible schedule that minimises the finishing time of the final activity, subject to precedence and resource availability.Each activity has a processing time, required resources, and predecessor activities; resource capacities are specified for each time period.Source: 1) The Resource-Constrained Project… · p. 4
  • The model is based on the single-mode RCPSP variant, with the planning horizon bounded by a makespan upper bound.The paper characterises the RCPSP as NP-hard.Source: 1) The Resource-Constrained Project… · pp. 3–4
  • The formalisation uses binary variables to indicate activity completion times, with constraints for scheduling each activity once, precedence, and renewable-resource limits.Each activity is assigned a time within its earliest-to-latest finishing-time window.Source: 1) The Resource-Constrained Project… · p. 4

2) The Degree Planning Problem:

The Degree Planning Problem (DPP) selects a semester-by-semester course plan that best matches a desired job’s required skills while satisfying degree regulations. Its MIP encoding represents scheduling, prerequisites, credits, availability, core units, and major requirements.

2) The Degree Planning Problem:

  • The DPP finds a feasible course schedule across semesters that best fits the skill levels required for a desired job.The plan must also satisfy academic regulations, and the paper’s formulation accounts for limited unit availability across semesters.Source: 2) The Degree Planning Problem · p. 4
  • The model represents units through their skills, achieved skill levels, credits, and semester availability, alongside precedence relationships, core units, and major requirements.A major includes core units and eligible-unit groups from which a specified number must be selected.Source: 2) The Degree Planning Problem · p. 4
  • The DPP objective minimises the distance between the desired job’s required skill levels and the levels acquired through the degree plan.The decision variables indicate whether each unit is planned in each semester.Source: 2) The Degree Planning Problem · pp. 4–5
  • The MIP constraints limit duplicate unit assignments, enforce semester credits and unit availability, and satisfy core-unit, precedence, and major requirements.Major requirements include completing at least one major, its core units, and a required number of eligible units.Source: 2) The Degree Planning Problem · p. 5
  • The DPP is formalised as a MIP for solvers such as CPLEX, and differs from the RCPSP because the two problems pursue different optimisation goals.The paper uses the two problems as complementary evaluation perspectives.Source: 2) The Degree Planning Problem · p. 5

C. Irreducible Infeasible Subsystem

An irreducible infeasible subsystem (IIS) identifies a minimal subset of constraints that is itself infeasible, while every proper subset is feasible. IISs help identify which constraints prevent feasibility, though finding them can be costly.

C. Irreducible Infeasible Subsystem

  • An IIS is an infeasible subset of constraints whose every proper subset is feasible.An infeasible system is a set of constraints for which no assignment satisfies them all.Source: C. Irreducible Infeasible Subsystem · p. 5
  • Finding an IIS identifies constraints that prevent a feasible solution and involves iteratively testing subsets for feasibility.The paper names the Deletion Filter, Additive Method, and a combination of both as approaches to finding IISs.Source: C. Irreducible Infeasible Subsystem · p. 5
  • Although computing IISs can be costly, state-of-the-art solvers efficiently compute them.Source: C. Irreducible Infeasible Subsystem · p. 5

III. BUILDING EXPLANATIONS FOR OPTIMISATION-BASED DECISIONS

LLMxMIP combines constraint reasoning with LLMs to explain optimisation-based decisions. It translates user questions into constraints on the MIP, enabling contrastive explanations about why a queried alternative is not at least as good as the optimum.

III. BUILDING EXPLANATIONS FOR OPTIMISATION-BASED DECISIONS

  • LLMxMIP combines constraint reasoning and LLMs to generate textual explanations, using the DPP as an illustrative example of a methodology intended for MIP applications across domains.The approach exploits how MIP constraints and objectives affect the solver’s output.Source: §III · pp. 5–6
  • A contrastive explanation addresses why a user-desired alternative is not at least as good as the optimal solution, rather than directly comparing the two solutions.The approach encodes the user’s query as additional optimisation constraints, similar to prior work that compares optimal and user-desired solutions,.Source: A. Query Translation · p. 6, §III · p. 6

A. Query Translation

  • Queries challenge assignments present in an optimal solution and are translated into enforce or veto constraints on the user-desired solution.The paper gives templates for DPP queries and states that the process of identifying queries, defining templates, and translating them into constraints generalises to other MIP problems.Source: A. Query Translation · p. 6

B. The User-Desired Satisfiability Problem

The User-Desired Satisfiability Problem (UDSP) tests whether a user’s requested alternative can satisfy the original constraints while matching or improving on the optimum. Rather than quantify how much worse an alternative is, the method identifies the constraints preventing it from being as good as the optimum.

B. The User-Desired Satisfiability Problem

where x are variables and (i) is a minimality constraint.6

  • The UDSP is a CSP whose constraints comprise the optimality condition, the main problem constraints, and the query constraints.The example identifies these as (i) the minimality constraint, (ii) the main problem constraints, and (iii) the query constraint.Source: B. The User-Desired Satisfiability… · p. 7, where x are variables and (i) is a… · p. 7
  • Instead of solving an extended optimisation problem or quantifying how much worse a requested alternative is, the method identifies why the query leads to worse solutions.The passage contrasts this approach with prior work that adds query constraints and compares the resulting solution with the original optimum,.Source: where x are variables and (i) is a… · p. 7

C. Computing the Infeasible Constraints

The method extracts an irreducible infeasible subsystem (IIS) from the UDSP, then organizes its constraints into a semantically labelled graph of reasons. The graph represents relationships among constraints to help an LLM explain why a requested alternative cannot be satisfied.

C. Computing the Infeasible Constraints

  • The method extracts an IIS, a minimal set of constraints that prevents a feasible UDSP solution, and uses its constraints to build explanations.The number of IISs can grow exponentially with constraint-set size, and different IISs can yield explanations of different sizes.Source: C. Computing the Infeasible Constraints · p. 7
  • The smallest IIS can yield a more concise explanation, but computing it is costly; CPLEX heuristics find a single IIS efficiently without guaranteeing it is smallest.In practice, CPLEX is observed to compute the smallest IIS for most instances at significantly lower computational cost.Source: C. Computing the Infeasible Constraints · p. 7
  • An infeasible UDSP’s IIS distinguishes query infeasibility from minimality infeasibility, depending on whether the optimality constraint appears in the conflicting constraints.Query infeasibility conflicts the query with main constraints; minimality infeasibility also includes the minimality constraint, indicating a compatible query yields a less optimal solution.Source: C. Computing the Infeasible Constraints · p. 8

D. Constructing the Graph of Reasons

  • The dual graph links constraints that share decision variables, representing their relationships within the IIS.Its vertices correspond to constraints, and an edge connects two constraints whose scopes overlap.Source: D. Constructing the Graph of Reasons · p. 8
  • The graph of reasons labels dual-graph constraints with natural-language templates, so nodes express reasons and edges retain their relationships.Constraints not directly related to the query can still connect to it through a path of dependencies.Source: D. Constructing the Graph of Reasons · pp. 8–9
  • The IIS dual graph is connected, and query translation and constraint labelling are the problem-dependent steps that require expert work.The remaining approach is described as domain-independent.Source: D. Constructing the Graph of Reasons · p. 9

E. Providing Textual Explanations with LLMs

LLMxMIP supplies an LLM with a structured, semantically characterized graph of reasons to guide textual explanations. In the example, this explanation is reported as correct and complete, while an unstructured LLM response accepts a false premise in a user’s query.

E. Providing Textual Explanations with LLMs

  • For an equally valid, equally optimal semester-3 alternative, direct prompting assumes the user’s premise is true and gives an incorrect explanation.LLMs may take assumptions in user prompts for granted rather than independently verifying their truthfulness.Source: E. Providing Textual Explanations with… · pp. 9–10
  • The graph of reasons guides the LLM toward correct textual explanations by structuring information extracted from the IIS.The paper identifies this structure as a response to LLM limitations in abstract reasoning and summarisation.Source: E. Providing Textual Explanations with… · p. 10
  • The prompt includes the optimisation problem context, optimal solution, user question, textual graph encoding, and task instructions.The graph encoding gives node labels and the relationships corresponding to graph edges.Source: E. Providing Textual Explanations with… · p. 10
  • The authors use zero-shot prompting to showcase LLM explanations rather than extensively evaluate prompting strategies.They note that prompt wording and formatting can affect output variability.Source: E. Providing Textual Explanations with… · p. 10
  • For the semester-4 query, the generated explanation is reported as correct and complete, mentioning all reasons in the graph.The example links prerequisite timing, seasonal restrictions, and the requirement to schedule subjects only once.Source: E. Providing Textual Explanations with… · p. 10

IV. EXPERIMENTAL EVALUATION

The evaluation is designed to assess explanation completeness and understandability, as well as the computational difficulty of producing explanations. It uses two optimisation scenarios: the DPP and the single-mode RCPSP.

IV. EXPERIMENTAL EVALUATION

  • The evaluation measures whether explanations are complete and easy to understand, and examines computational hardness to characterize which instances can be handled in real time.The evaluation covers both explanation quality and computational performance.Source: §IV · p. 10

A. Experimental Setting

  • The two scenarios are selected to demonstrate applicability to real-world problems and evaluate scalability on computationally hard instances.The evaluation uses the DPP and RCPSP for these complementary purposes.Source: 1) Optimisation-Based Benchmark… · p. 10

1) Optimisation-Based Benchmark Scenarios:

2) Experimental Methodology:

The evaluation compares graph-of-reasons prompts with IIS-only prompts on completeness and readability in the DPP and RCPSP. Graphs improve average completeness in both domains; readability is similar for the DPP and better for the RCPSP.

2) Experimental Methodology:

  • The study generated DPP queries for 118 jobs and selected 130 distinct queries per domain for paired explanation comparisons.For the DPP, five queries per each of ten query types yielded 5,900 queries overall; the representative sample was selected to include different query constraints and nonempty IISs.Source: 2) Experimental Methodology · p. 11
  • The prompts supplied either semantically rendered IIS constraints alone or the same constraints with graph nodes and their relationships.Completeness measures the percentage of IIS reasons mentioned; readability uses Gunning Fog Index and word count.Source: 2) Experimental Methodology · p. 11

B. Completeness and Readability Results

  • DPP explanations averaged 84% completeness with a graph of reasons versus 64% with an IIS, a statistically significant 20% gain; they were 32% longer while GFI readability remained similar.The comparison covers 65 pairs of explanations across both domains.Source: B. Completeness and Readability Results · p. 11, Table VII · p. 12
  • RCPSP explanations averaged 85% completeness with a graph of reasons versus 69% with an IIS, a 16% gain, and had better readability: GFI 15.6 versus 16.5.The graph-prompt explanations were easier to understand by the GFI measure.Source: B. Completeness and Readability Results · pp. 11–12, Table VII · p. 12
  • For medium and large explanations, graph prompts mentioned about 30% and 20% more reasons, respectively, than IIS prompts; small explanations could be complete without a graph.The groups contain fewer than five, five to ten, and more than ten reasons; Figure 4 aggregates completeness across both domains.Source: B. Completeness and Readability Results · p. 12, Figure 4 · p. 12

C. Empirical Hardness Results

The study compares IIS computation time with MIP solving time, treating their ratio as the explanation-time overhead. IIS computation is often quick, particularly for the RCPSP, though some query types are harder than others.

C. Empirical Hardness Results

  • For DPP instances, solving and IIS computation took ∼10−2 seconds in most cases; average explanation overhead was close to 100%, and only 25% took more than twice MIP solving time.Source: C. Empirical Hardness Results · p. 13
  • The study leaves the reasons for unusually hard query types in both domains—DPP Q6 and RCPSP Q3—for future work.The explanation for Q6's greater difficulty remains to be established; the RCPSP discussion similarly identifies Q3 as harder than others.Source: C. Empirical Hardness Results · pp. 13–14
  • For RCPSP, median explanation overhead was 6.7% and median IIS time was 3.3 seconds, versus 31.2 seconds median MIP solving time; over 75% of explanations took under one minute.In most cases, overhead was below 40%.Source: C. Empirical Hardness Results · p. 13, Figure 7 · p. 13
  • For RCPSP, most query types averaged under 60 seconds and had under 10% overhead, though some, such as Q3, were substantially harder.The overhead is the ratio of IIS computation time to optimal-solution computation time; graph construction and LLM text generation were treated as negligible relative to maximum IIS runtimes.Source: C. Empirical Hardness Results · pp. 12–13, Figure 8 · p. 13

V. RELATED WORK

Related work contrasts LLMxMIP with what-if and constraint-analysis approaches; the conclusion reports improved explanation quality and speed on scheduling problems, alongside planned user evaluation and broader applications.

V. RELATED WORK

  • Georgara et al. use numerical rather than causal reasons, while Korikov et al., specify numerical changes; these approaches are domain-specific and use abstract representations or fixed templates.LLMxMIP is presented as a domain-independent approach that produces natural-language explanations.Source: §V · p. 14
  • LLMxMIP’s explanations are contrastive, social, and selected, and link constraints and the objective function to the optimisation output.The paper relates these properties to Miller et al.’s account of useful explanations.Source: §V · p. 14
  • Vasileiou et al. pass MUS constraints to an LLM without their relationships; LLMxMIP instead uses an IIS of a specially defined CSP and a graph of reasons to explain optimal-solution queries.The paper reports a measurable benefit over directly providing the IIS, especially for medium-large explanations.Source: §V · p. 14

VI. CONCLUSIONS AND FUTURE WORK

  • The graph of reasons significantly improves explanation completeness and readability; explanations run in real time in most cases, and RCPSP explanations are faster than solving hard instances.Previous approaches, require re-solving the optimisation problem to generate explanations.Source: §VI · p. 15
  • The authors plan a user study of degree-planning explanations and applications to research project planning and value-systems aggregation for policymakers.The proposed study would assess satisfaction, usefulness, and completeness.Source: §VI · p. 15

DATA AVAILABILITY

APPENDIX A IIS EXAMPLE

The appendices document an IIS example, RCPSP query encodings and constraint labels, and two prompts that differ in how they present relationships among reasons.

APPENDIX A IIS EXAMPLE

  • Precedence constraints c5, c6, and c7 each comprise multiple mathematical constraints, which the example combines into one restriction to enforce semester-level planning requirements.This represents the requirement to plan a subject after completing its prerequisite.Source: Appendix A · p. 17, Table A1 · p. 17

APPENDIX B RCPSP QUERY TRANSLATION

APPENDIX C RCPSP CONSTRAINT LABELS

APPENDIX D LLM PROMPT

  • The two running-example prompts differ in that the graph prompt displays connections among reasons, orders constraints by scope, and explains their graph-like relation to the LLM.The comparison prompt supplies translated IIS constraints without the connections; the example query asks why Programming Fundamentals is not planned in semester 4.Source: Appendix D · pp. 17–18

Related papers

Loading 2610.31119v1…