1 Search Results for "Garuba, Francis"


Document
Robust Network Capacity Expansion with Non-Linear Costs

Authors: Francis Garuba, Marc Goerigk, and Peter Jacko

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)


Abstract
The network capacity expansion problem is a key network optimization problem practitioners regularly face. There is an uncertainty associated with the future traffic demand, which we address using a scenario-based robust optimization approach. In most literature on network design, the costs are assumed to be linear functions of the added capacity, which is not true in practice. To address this, two non-linear cost functions are investigated: (i) a linear cost with a fixed charge that is triggered if any arc capacity is modified, and (ii) its generalization to piecewise-linear costs. The resulting mixed-integer programming model is developed with the objective of minimizing the costs. Numerical experiments were carried out for networks taken from the SNDlib database. We show that networks of realistic sizes can be designed using non-linear cost functions on a standard computer in a practical amount of time within negligible suboptimality. Although solution times increase in comparison to a linear-cost or to a non-robust model, we find solutions to be beneficial in practice. We further illustrate that including additional scenarios follows the law of diminishing returns, indicating that little is gained by considering more than a handful of scenarios. Finally, we show that the results of a robust optimization model compare favourably to the traditional deterministic model optimized for the best-case, expected, or worst-case traffic demand, suggesting that it should be used whenever computationally feasible.

Cite as

Francis Garuba, Marc Goerigk, and Peter Jacko. Robust Network Capacity Expansion with Non-Linear Costs. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{garuba_et_al:OASIcs.ATMOS.2019.5,
  author =	{Garuba, Francis and Goerigk, Marc and Jacko, Peter},
  title =	{{Robust Network Capacity Expansion with Non-Linear Costs}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{5:1--5:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.5},
  URN =		{urn:nbn:de:0030-drops-114175},
  doi =		{10.4230/OASIcs.ATMOS.2019.5},
  annote =	{Keywords: Robust Optimization, Mobile Network, Network Capacity Design \& Expansion, Non-linear Cost, Traffic and Transport Routing}
}
  • Refine by Author
  • 1 Garuba, Francis
  • 1 Goerigk, Marc
  • 1 Jacko, Peter

  • Refine by Classification
  • 1 Networks
  • 1 Theory of computation → Continuous optimization
  • 1 Theory of computation → Network optimization

  • Refine by Keyword
  • 1 Mobile Network
  • 1 Network Capacity Design & Expansion
  • 1 Non-linear Cost
  • 1 Robust Optimization
  • 1 Traffic and Transport Routing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail