Source-linked AI summary
Counterfactual Routing Using Integer Programming with Constraint Generation
Daniël Vos, Sterre Lutz
TL;DR
The paper addresses how to produce transparent counterfactual explanations showing what minimal road-network changes would make a user’s route optimal. It models the task as an integer program with iteratively generated constraints and finds solutions quickly, ranking fourth in quality while being fastest on every held-out instance. The method nevertheless solves a restriction of the competition problem because it disallows route-distance slack.
Problem
Counterfactual routing seeks minimal road-network changes that make a user-selected route the shortest, providing explanations for why an alternative route would be optimal under changed conditions.
Method
The approach formulates counterfactual routing as an integer program and iteratively adds constraints using solver callbacks and shortest-path checks.
Results
Fourth-place solution quality was achieved on held-out test instances, while the method was fastest on every instance, averaging 9.0 seconds versus 118.8 seconds for the next-fastest submission.
Takeaways & Limitations
The constraint-generation approach provides exact counterfactual solutions with strong runtime performance on the competition’s evaluated instances.
Takeaways & Limitations
The method solves a restriction that requires the user’s route itself to become shortest, whereas the competition permits route-distance slack; future work should search over target routes.
Abstract
from arXiv · showhide
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.
1 Introduction
The competition targets transparent counterfactual explanations for accessible routing by finding minimal road-network changes that make a user’s chosen route optimal. The submission formulates this task as an integer program with iterative constraint incorporation and achieved fourth-place solution quality while being fastest on every held-out instance.
- Wheelchair-accessible routing must account for curb heights, sidewalk widths, and crossings in addition to reaching destinations quickly.
- Existing constrained routing algorithms can find optimal paths but often do not explain why one route is preferred, potentially undermining user trust.
- Counterfactual explanations identify minimal road-network changes under which a chosen foil route would become optimal.
- The solution models counterfactual routing as an integer program and iteratively adds constraints until the modified route becomes optimal.
- Fourth-place solution quality was achieved on held-out test instances, while the method was fastest on every instance.Average runtime was 9.0 seconds, compared with 118.8 seconds for the next-fastest submission.
2 Problem Description
The task is to minimally modify an Amsterdam road-map segment so a user-defined foil route becomes the shortest path between two points. The formulation represents roads and accessibility attributes explicitly, measures graph and route differences, and optimizes the number of changes without route-distance slack.
- Given an Amsterdam road-map segment and a user-defined foil route, the task is to make minimal changes so that route becomes shortest from A to B.
- The neighborhood is modeled as a multigraph G = {V, E}, with nodes as locations, edges as roads or paths, and edge attributes including length, width, curb height, and path type.
- The graph-distance objective counts operations needed to transform the original graph into a counterfactual graph.
- Allowed graph operations change an edge’s type, minimum width, or maximum curb height, thereby modifying edge weights and potentially the minimum-weight path.
- The route-distance function is the weighted common edge rate, which measures the lengths of edges shared by two paths.
- The concrete optimization minimizes the number of graph changes and disallows the competition’s 0.05 route-distance slack for a simpler formulation.
3 Method Description
The method formulates counterfactual routing as an integer program that minimizes graph modifications while enforcing the user’s foil route as shortest. Constraint generation adds only violated shortest-path constraints during solving, avoiding explicit enumeration of all simple paths.
- Integer-program formulation: The integer program minimizes operations that change edge weights or enable or disable edges, accounting for edges requiring multiple operations.Three binary variables indicate weight changes, enabling, and disabling; constants Ce capture the number of operations needed to enable an edge.
- Integer-program formulation: The formulation enforces the foil route’s weight to be strictly lower than every other simple path.A small constant ϵ enforces strict inequality, while path weights remain linear in the decision variables.
- Constraint generation: Because enumerating all simple paths can make the ILP exponentially large, the method adds only necessary constraints through iterative constraint generation.The process begins with an empty formulation and adds shortest-path constraints until the foil route becomes shortest.
- Constraint generation: Solver callbacks test each integer assignment by applying its operations and running Dijkstra to find the current least-weight path.If that path is not the foil route, the callback adds a constraint and continues solving; otherwise, the solution is accepted.
- Constraint generation: The approach usually needs relatively few added constraints, but instances with a large initial gap between the foil and shortest routes take substantially longer.This runtime behavior is attributed to the relative weight of the user’s foil route compared with the optimal route.
4 Results
The method was evaluated on 25 competition instances across five maps and five foil routes per map. It solved every instance within 10 seconds in the train-set evaluation and ranked fourth in solution quality while being fastest on every held-out test instance.
- Evaluation setup: The evaluation used 25 instances comprising five maps with five foil routes each.Experiments ran on Windows 11 with a 13th Gen Intel Core i7-1365U processor and 16 GB RAM.
- Runtime: The method solved all train-set instances within 10 seconds.Setup required 0.5 to 2 seconds per instance, with remaining time spent in the solver; the slowest instance took roughly 8 seconds.
- Competition results: Fourth place in solution quality was achieved in the final held-out evaluation.This result concerns the competition’s final test instances.
- Competition results: 9.0 seconds was the average runtime, versus 118.8 seconds for the next-fastest submission, while remaining fastest on every test instance.The comparison is reported for the final competition evaluation on held-out test instances.
5 Future Work
Future work should extend the method from exact foil-route optimality to the competition’s slack-based objective. The proposed extension searches nearby target routes, solves a minimal counterfactual for each, and returns the smallest one.
- Scope boundary: The current method solves a restricted problem requiring the foil route itself to become the shortest route.The competition permits slack between the shortest path and the user’s route.
- Proposed extension: The recommended extension enumerates target routes close to the foil path and applies the method to each candidate.Candidate routes should satisfy dr ≤ δ.
- Proposed extension: The smallest counterfactual found across the enumerated target routes can be returned.Warm starts and memorized constraints are expected to improve solving time during this search.