A Primal-Dual Approach to Markovian Network Optimization

Yue Yu, Dan Calderone, Sarah H. Q. Li, Lillian J. Ratliff, Behçet Açıkmeşe

Published 2019-01-25Version 1

We formulate a novel class of stochastic network optimization problems, termed Markovian network optimization, as a primal-dual pair, whose solutions are characterized by the Kolmogorov equation, the Bellman equation, and generalized Ohm's law. We further generalize such network optimization to accommodate variable divergence---i.e., total flow in the network is variable---and multi-commodity flows with heterogeneous planning horizons, features that are well-motivated in applications arise from game-theoretic settings. Finally, in order to solve the primal-dual pair, we design dynamic programming based numerical algorithms that outperform state-of-the-art commercial software (Gurobi) in extensive numerical experiments.