Denoising noisy route costs improves shortest path results
Eigenvalue-Decomposition Cost Denoising as an Alternative to Predict-then-Optimize for Shortest-Path Problems
Machine Learning
Summary
Finding the best route when the costs of roads are uncertain can be tricky. The paper looks at a common method that predicts these costs based on context but struggles if the predictions are too simple. Instead, the authors suggest cleaning up the noisy cost data itself by using a mathematical technique called eigenvalue decomposition, which finds patterns in the noise before making decisions. In tests on a grid network, this denoising method performed better than prediction-based approaches, especially when the prediction model was less accurate.
What this means in practice
- •For logistics planners: Improve route selection by denoising uncertain travel cost data before shortest path calculations.
- •For network operators: Enhance network routing by applying cost denoising to repeated noisy measurements to reduce routing errors.
Authors
Henry Aldridge-Krawciw, Irene Aldridge
Abstract
Predict-then-optimize methods such as Smart "Predict, then Optimize" (SPO+) of Elmachtoub and Grigas (2022) learn a mapping from contextual features to unknown edge costs and then solve the induced combinatorial problem on the predicted costs. This approach is powerful but relies on the predictive model being well specified: when the true cost-generating process is nonlinear in the features and the predictor is linear, SPO+'s performance degrades as the misspecification grows. We propose and evaluate a structurally different remedy for a specific but common setting: when the decision-maker observes many noisy realizations of the same underlying cost process, the realized cost vectors themselves can be treated as a noisy signal and denoised directly, via eigenvalue decomposition (equivalently, Principal Component Analysis) of their covariance matrix, before ever invoking a predictive model. We instantiate this idea on the $5\times5$ grid shortest-path benchmark introduced by Elmachtoub and Grigas (2022), retaining only the top-$k$ eigenvectors of the training cost covariance matrix and projecting new noisy cost observations onto that subspace prior to solving with Dijkstra's (1959) algorithm. We find that the choice of $k$ is decisive: keeping only $k{=}2$ eigenvectors discards real signal and underperforms even the naive noisy-cost baseline, while setting $k{=}5$ to match the true latent feature dimension makes eigenvalue-denoised Dijkstra the best-performing method at every misspecification level tested, outperforming SPO+ by a wide margin under high misspecification.