{
  "id": "1901.08731",
  "version": "v1",
  "published": "2019-01-25T04:19:24.000Z",
  "updated": "2019-01-25T04:19:24.000Z",
  "title": "A Primal-Dual Approach to Markovian Network Optimization",
  "authors": [
    "Yue Yu",
    "Dan Calderone",
    "Sarah H. Q. Li",
    "Lillian J. Ratliff",
    "Behçet Açıkmeşe"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-01-25T04:19:24.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "primal-dual approach",
      "primal-dual pair",
      "outperform state-of-the-art commercial software",
      "stochastic network optimization problems",
      "termed markovian network optimization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}