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 -