2021/08/17 by Liu, Pengfei
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2108.07549
This paper introduces a novel theoretical framework and a suite of highly efficient, parallelizable algorithms for solving the large-scale multicommodity flow (MCF) feasibility problem. We reframe the classical constraint-satisfaction problem as an equilibrium search. By defining vertex-specific height functions and edge-specific congestion functions, we establish a new, intuitive optimality condition: a flow is feasible if and only if it corresponds to a zero-stable pseudo-flow, where all potential differences across the network are resolved. This condition gives rise to an edge-separable convex optimization problem, whose structure is inherently suited for massive parallelization. Based on this formulation, we develop a family of Potential Difference Reduction (PDR) algorithms. Our primary method, provably convergent, solves an exact quadratic programming subproblem for each edge in parallel. To address scenarios with a very large number of commodities, we propose two computationally cheaper heuristics based on adaptive gradient descent. Extensive numerical experiments on well-known benchmarks demonstrate the framework's remarkable performance. This work provides a powerful new approach for tackling large-scale MCF problems, while also identifying the formal analysis of the convergence rate as a promising direction for future research.