跳转至

使用约束生成整数规划的反事实路由

文章背景与核心概要

本文介绍了 Daniël Vos 和 Sterre Lutz 为 IJCAI 2025《反事实路由竞赛》（CRC 25）所提交的参赛方案。该研究主要解决最短路径问题中的反事实解释挑战，具体而言，即确定在道路网络中所需要进行的最小修改，从而使用户选择的路线成为最优路线（例如：“如果X道路不是自行车道，你建议的路线确实将是最优路线”）。

作者提出将该问题建模为整数规划，并迭代应用约束生成技术，直至找到精确解。在竞赛针对未公开测试实例的最终评估中，该方法在解的质量上取得了第四名，并在每一个测试实例上都实现了最快的运行时间。其平均运行时间仅为 9.0 秒，而排名第二快的提交方案则高达 118.8 秒。

摘要

Summary

This paper presents the submission by Daniël Vos and Sterre Lutz to the IJCAI 2025 Counterfactual Routing Competition (CRC 25). The research addresses the challenge of finding counterfactual explanations for the shortest path problem—specifically, determining the minimal modifications required in a road network to make a user-chosen route the optimal one (e.g., "Your suggested route would indeed have been optimal, if road X were not a bicycle path"). The authors propose modeling the problem as an integer program, iteratively applying constraint generation until an exact solution is discovered. In the competition's final evaluation on held-out test instances, their method achieved fourth place in solution quality and the fastest runtime on every single instance, averaging 9.0 seconds compared to 118.8 seconds for the next-fastest submission.

元数据与文档信息

Metadata & Document Information

  • 主要学科: 人工智能 (cs.AI)
  • Primary Subject: Artificial Intelligence (cs.AI)
  • 次要学科: 数据结构与算法 (cs.DS)
  • Secondary Subject: Data Structures and Algorithms (cs.DS)
  • 提交日期: 2026年9月3日
  • Submission Date: 3 September 2026
  • 作者: Daniël Vos, Sterre Lutz
  • Authors: Daniël Vos, Sterre Lutz

链接与资源