A scalable descent algorithm for network design problems

In a network design problem (NDP), a traffic planner aims to improve the performance of a transportation network by anticipating and manipulating the Wardrop equilibrium (WE) state achieved by the travelers. A critical challenge in solving NDPs lies in computing the derivatives of their objectives, which, according to the chain rule, further requires the gradient of WE. In the literature, this is a long-standing computational bottleneck that has limited the application of general descent algorithms to NDPs. Recently, many have attempted to compute the gradient of WE by unrolling a numerical algorithm that solves WE with automatic differentiation (AD) tools. Although these methods have better time efficiency than conventional benchmarks, they still face severe memory constraints from storing the full computational process for solving WE. In this work, we find that unrolling fixed-point iterations of a WE solver initialized at a WE solution also provides exact WE gradients. We further develop an unrolling scheme whose time efficiency is identical to AD-based approaches. Yet, by recognizing each fixed-point iteration as identical, our method requires only single-iteration memory storage, which is a dramatic improvement over AD-based approaches. Numerical experiments across classical NDP benchmarks confirm our method’s superior scalability.