### 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 language | English (US) |
---|---|

Journal | Journal of Optimization Theory and Applications |

DOIs | |

State | Published - Jan 1 2019 |

### Fingerprint

### Keywords

- ADMM
- Convex optimization
- Network flow
- Robust optimization

### Cite this

*Journal of Optimization Theory and Applications*. https://doi.org/10.1007/s10957-019-01528-5

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

Research output: Contribution to journal › Article

*Journal of Optimization Theory and Applications*. https://doi.org/10.1007/s10957-019-01528-5

}

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

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

SN - 0022-3239

ER -