Accepted author manuscript, 463 KB, PDF document
Available under license: CC BY: Creative Commons Attribution 4.0 International License
Final published version
Licence: CC BY: Creative Commons Attribution 4.0 International License
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Robust Network Capacity Expansion with Non-linear Costs. / Garuba, Francis; Goerigk, Marc; Jacko, Peter.
19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2019. ed. / Valentina Cacchiani; Alberto Marchetti-Spaccamela. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019. p. 5.1-5.13 (OASICS; Vol. 75).Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
}
TY - GEN
T1 - Robust Network Capacity Expansion with Non-linear Costs
AU - Garuba, Francis
AU - Goerigk, Marc
AU - Jacko, Peter
PY - 2019/11/15
Y1 - 2019/11/15
N2 - 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.
AB - 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.
KW - Robust Optimization
KW - Mobile Network
KW - Network Capacity Design & Expansion
KW - Non-linear Cost
KW - Traffic and Transport Routing
U2 - 10.4230/OASIcs.ATMOS.2019.5
DO - 10.4230/OASIcs.ATMOS.2019.5
M3 - Conference contribution/Paper
T3 - OASICS
SP - 5.1-5.13
BT - 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2019
A2 - Cacchiani, Valentina
A2 - Marchetti-Spaccamela, Alberto
PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
T2 - ALGO 2019
Y2 - 9 September 2019 through 13 September 2019
ER -