A Distributed Method for Optimal Capacity Reservation

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

Research output: Contribution to journalArticle

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)
JournalJournal of Optimization Theory and Applications
DOIs
StatePublished - Jan 1 2019

Fingerprint

Reservation
Parallel algorithms
Costs
Scenarios
Distributed Algorithms
Linear Program
Alternate
Choose
Optimal capacity
Minimise

Keywords

  • ADMM
  • Convex optimization
  • Network flow
  • Robust optimization

Cite this

A Distributed Method for Optimal Capacity Reservation. / Moehle, Nicholas; Shen, Xinyue; Luo, Zhi-Quan; Boyd, Stephen.

In: Journal of Optimization Theory and Applications, 01.01.2019.

Research output: Contribution to journalArticle

Moehle, Nicholas ; Shen, Xinyue ; Luo, Zhi-Quan ; Boyd, Stephen. / A Distributed Method for Optimal Capacity Reservation. In: Journal of Optimization Theory and Applications. 2019.
@article{baee1e6341cc45cfaa6490936050fa16,
title = "A Distributed Method for Optimal Capacity Reservation",
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.",
keywords = "ADMM, Convex optimization, Network flow, Robust optimization",
author = "Nicholas Moehle and Xinyue Shen and Zhi-Quan Luo and Stephen Boyd",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/s10957-019-01528-5",
language = "English (US)",
journal = "Journal of Optimization Theory and Applications",
issn = "0022-3239",
publisher = "Springer New York",

}

TY - JOUR

T1 - A Distributed Method for Optimal Capacity Reservation

AU - Moehle, Nicholas

AU - Shen, Xinyue

AU - Luo, Zhi-Quan

AU - Boyd, Stephen

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - ADMM

KW - Convex optimization

KW - Network flow

KW - Robust optimization

UR - http://www.scopus.com/inward/record.url?scp=85065594817&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065594817&partnerID=8YFLogxK

U2 - 10.1007/s10957-019-01528-5

DO - 10.1007/s10957-019-01528-5

M3 - Article

AN - SCOPUS:85065594817

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

SN - 0022-3239

ER -