用约束推理生成MILP问题的可解释图谱，帮用户理解决策原因。
Exploiting Constraint Reasoning to Build Graphical Explanations for Mixed-Integer Linear Programming
- 将用户提问转化为约束，通过IIS找出不可行根源
- 计算出的IIS能揭示导致解不成立的关键约束集合
- 适合需要解释优化决策的工程师与管理者
随着可信AI的发展，对优化问题（尤其是以MILP形式建模的决策过程）的对比解释技术日益受到关注。本文提出X-MILP，一种无需领域知识的MILP对比解释方法，基于约束推理构建解释。首先，将用户关于MILP解的疑问转化为额外约束；其次，通过计算新约束集的不可约不可行子系统（IIS）来确定回答用户问题的原因；最后，将IIS组织为“原因图”，展示各原因之间的结构关系，帮助用户理解解释逻辑。我们在多个经典优化问题实例上测试了该方法，评估了解释生成的实证难度。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。