.png){kind=icon}
Return
Exploiting Constraint Reasoning to Build Graphical Explanations for Mixed-Integer Linear Programming
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-01399-6_2.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 XMILP, 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.
Keywords:
Explainability
Constraint Reasoning
Mixed-Integer Linear Programming
Journal
E
IF:
0
Papers:
13
Citations:
0
Organization
Cited Papers
ShareSaveShareSaveA branch and bound algorithm for extracting smallest minimal unsatisfiable subformulas.png)
Constraints
ConstraintsIF0
PREAI
ShareSaveShareSaveShareSave
View more