A Distributed Method for Optimal Capacity Reservation

Nicholas Moehle, Xinyue Shen, Zhi Quan Luo, Stephen Boyd

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

We consider the problem of reserving link capacity in a network in such a way that any of a given set of flow scenarios can be supported. In the optimal capacity reservation problem, we choose the reserved link capacities to minimize the reservation cost. This problem reduces to a large linear program, with the number of variables and constraints on the order of the number of links times the number of scenarios. We develop a scalable, distributed algorithm for the problem that alternates between solving (in parallel) one-flow problem per scenario, and coordination steps, which connect the individual flows and the reservation capacities.

Original languageEnglish (US)
Pages (from-to)1130-1149
Number of pages20
JournalJournal of Optimization Theory and Applications
Volume182
Issue number3
DOIs
StatePublished - Sep 15 2019

Keywords

  • ADMM
  • Convex optimization
  • Network flow
  • Robust optimization

Fingerprint

Dive into the research topics of 'A Distributed Method for Optimal Capacity Reservation'. Together they form a unique fingerprint.

Cite this