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

• URL: http://arxiv.org/abs/2507.13007v1
• Date: Thu, 17 Jul 2025 11:25:33 GMT
• Title: Exploiting Constraint Reasoning to Build Graphical Explanations for Mixed-Integer Linear Programming
• Authors: Roger Xavier Lera-Leri, Filippo Bistaffa, Athina Georgara, Juan Antonio Rodriguez-Aguilar,
• Abstract summary: X-MILP is a domain-agnostic approach for building contrastive explanations for MILPs.<n>First, we show how to encode the queries a user makes about the solution of an MILP problem as additional constraints.<n>Then, we determine the reasons that constitute the answer to the user's query by computing the Irreducible Infeasible Subsystem (IIS)
• Score: 0.6749750044497732
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• PixelThink: Towards Efficient Chain-of-Pixel Reasoning [70.32510083790069]
  PixelThink is a simple yet effective scheme that integrates externally estimated task difficulty and internally measured model uncertainty.<n>It learns to compress reasoning length in accordance with scene complexity and predictive confidence.<n> Experimental results demonstrate that the proposed approach improves both reasoning efficiency and overall segmentation performance.
  arXiv  Detail & Related papers  (2025-05-29T17:55:49Z)
• Make LLMs better zero-shot reasoners: Structure-orientated autonomous reasoning [52.83539473110143]
  We introduce a novel structure-oriented analysis method to help Large Language Models (LLMs) better understand a question. To further improve the reliability in complex question-answering tasks, we propose a multi-agent reasoning system, Structure-oriented Autonomous Reasoning Agents (SARA) Extensive experiments verify the effectiveness of the proposed reasoning system. Surprisingly, in some cases, the system even surpasses few-shot methods.
  arXiv  Detail & Related papers  (2024-10-18T05:30:33Z)
• Explainable Data-Driven Optimization: From Context to Decision and Back Again [76.84947521482631]
  Data-driven optimization uses contextual information and machine learning algorithms to find solutions to decision problems with uncertain parameters. We introduce a counterfactual explanation methodology tailored to explain solutions to data-driven problems. We demonstrate our approach by explaining key problems in operations management such as inventory management and routing.
  arXiv  Detail & Related papers  (2023-01-24T15:25:16Z)
• Finding Counterfactual Explanations through Constraint Relaxations [6.961253535504979]
  Interactive constraint systems often suffer from infeasibility (no solution) due to conflicting user constraints. A common approach to recover infeasibility is to eliminate the constraints that cause the conflicts in the system. We propose an iterative method based on conflict detection and maximal relaxations in over-constrained constraint satisfaction problems.
  arXiv  Detail & Related papers  (2022-04-07T13:18:54Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  We introduce a new model-oriented approach for Answer Set Programming that lifts the Symmetry Breaking Constraints into a set of interpretable first-order constraints. Experiments demonstrate the ability of our framework to learn general constraints from instance-specific SBCs.
  arXiv  Detail & Related papers  (2021-12-22T11:27:48Z)
• Counterfactual Explanations in Sequential Decision Making Under Uncertainty [27.763369810430653]
  We develop methods to find counterfactual explanations for sequential decision making processes. In our problem formulation, the counterfactual explanation specifies an alternative sequence of actions differing in at most k actions. We show that our algorithm finds can provide valuable insights to enhance decision making under uncertainty.
  arXiv  Detail & Related papers  (2021-07-06T17:38:19Z)
• Regret Analysis in Deterministic Reinforcement Learning [78.31410227443102]
  We study the problem of regret, which is central to the analysis and design of optimal learning algorithms. We present logarithmic problem-specific regret lower bounds that explicitly depend on the system parameter.
  arXiv  Detail & Related papers  (2021-06-27T23:41:57Z)
• Discrete Reasoning Templates for Natural Language Understanding [79.07883990966077]
  We present an approach that reasons about complex questions by decomposing them to simpler subquestions. We derive the final answer according to instructions in a predefined reasoning template. We show that our approach is competitive with the state-of-the-art while being interpretable and requires little supervision.
  arXiv  Detail & Related papers  (2021-04-05T18:56:56Z)
• Identification of Unexpected Decisions in Partially Observable Monte-Carlo Planning: a Rule-Based Approach [78.05638156687343]
  We propose a methodology for analyzing POMCP policies by inspecting their traces. The proposed method explores local properties of policy behavior to identify unexpected decisions. We evaluate our approach on Tiger, a standard benchmark for POMDPs, and a real-world problem related to mobile robot navigation.
  arXiv  Detail & Related papers  (2020-12-23T15:09:28Z)
• A framework for step-wise explaining how to solve constraint satisfaction problems [21.96171133035504]
  We study the problem of explaining the inference steps that one can take during propagation, in a way that is easy to interpret for a person. Thereby, we aim to give the constraint solver explainable agency, which can help in building trust in the solver.
  arXiv  Detail & Related papers  (2020-06-11T11:35:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.