A distributed method for optimal capacity reservation

DOI10.1007/S10957-019-01528-5MaRDI QIDQ2322374zbMATH OpenOpenAlexWikidataFDO

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

Publication date 4 September 2019

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.00677

zbMATH Keywords

ADMMconvex optimizationnetwork flowrobust optimization

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90)

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. Small and medium size problems are within the capabilities of generic linear program solvers. We develop a more 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.

Recommendations

• A distributed approach to capacity allocation in logical networks
• Reserving resilient capacity in a network
• An optimal distributed routing algorithm using dual decomposition techniques
• scientific article; zbMATH DE number 3908345
• Routing and Capacity Allocation in Networks with Trunk Reservation

Cites work

• Affine recourse for the robust network design problem: between static and dynamic routing
• An Application of Generalized Linear Programming to Network Flows
• An approach to robust network design in telecommunications
• CVXPY: a Python-embedded modeling language for convex optimization
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Hardness of robust network design
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Optimum Synthesis of a Network with Non-Simultaneous Multicommodity Flow Requirements
• Robust optimization
• Routing of uncertain traffic demands
• Synthesis of a Communication Network

Cited in

(5)

• A distributed approach to capacity allocation in logical networks
• Dynamic capacity allocation for group bookings in live entertainment
• Estimating aggregate resource reservation for dynamic, scalable, and fair distribution of bandwidth
• Reserving resilient capacity for a single commodity with upper-bound constraints
• Distance vector-based advance reservation with delay performance guarantees

Describes a project that uses

Uses Software

• CVXPY
• ECOS

This page was built for publication: A distributed method for optimal capacity reservation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2322374)