Beyond Solving: Prescriptive Probing for Neural Routing Solvers

Abstract:Neural combinatorial optimization (NCO) trains fast heuristics for routing problems, but planners often need more than a single solve: they ask which stop to drop, which transition to preserve, or which subset of stops to remove if a route is infeasible. Answering such counterfactual questions by re-solving each candidate is expensive even when the action set is small. We introduce Prescriptive Probing: using the frozen representations of a trained NCO model to rank candidate interventions for what-if decision support. While recent interpretability work descriptively probes what NCO solvers encode, we ask whether those same representations can prescriptively guide intervention choices on real-road routing problems. Where exhaustive labels are available, we train supervised probes from offline re-solve labels; where they are not (e.g., combinatorial action spaces), we train a lightweight reinforcement learning intervention head. Across real-road benchmarks on the Asymmetric Traveling Salesperson Problem and Capacitated Vehicle Routing Problem, probes built on frozen model representations achieve the strongest performance on a majority of intervention tasks and improve over local-repair heuristics on edge-forbiddance and on key node- and multi-node-removal metrics. We further investigate probeability as a property of the routing model itself, varying model quality, the mix of supervised learning and reinforcement learning, and the architecture family. Overall, our results suggest a new use case for NCO solvers: representations learned for route construction can transfer to decision support.

Machine Learning (cs.LG)

arXiv:2602.07216 [cs.LG]

(or arXiv:2602.07216v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2602.07216 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.