Search papers, labs, and topics across Lattice.
This paper addresses the challenge of generating counterfactual explanations for the shortest path problem in road networks, a task central to the IJCAI 2025 Counterfactual Routing Competition. By modeling the problem as an integer programming task and employing an iterative constraint generation approach, the authors achieved a solution that not only ranked fourth in overall quality but also outperformed competitors in speed, with an average runtime of 9.0 seconds. This work highlights the potential for efficient counterfactual reasoning in routing applications, providing insights into optimal path adjustments based on user preferences.
Fast and effective counterfactual explanations for routing decisions can be achieved through innovative integer programming techniques, outperforming traditional methods by a significant margin.
We present our submission to the IJCAI 2025'Counterfactual Routing Competition'(CRC 25). The goal of the competition is to find counterfactual explanations for the shortest path problem. This requires deciding what the minimal changes to a road network would make a route chosen by the user the optimal route. This enables explanations such as"Your suggested route would indeed have been optimal, if road X were not a bicycle path."Our solution models the problem as an integer program, iteratively incorporating constraints until an exact solution is found. In the final evaluation on held-out test instances, our method ranked fourth in solution quality and obtained its solution fastest on every instance, with an average runtime of 9.0 seconds compared to 118.8 seconds for the next-fastest submission.
