Optimization Online


Robust network design with uncertain outsourcing cost

Artur Alves Pessoa(artur.a.pessoa***at***gmail.com)
Michael Poss(mjposs***at***gmail.com)

Abstract: The expansion of a telecommunications network faces two sources of uncertainty, which are the demand for traffic that shall transit through the expanded network and the outsourcing cost that the network operator will have to pay to handle the traffic that exceeds the capacity of its network. The latter is determined by the future cost of telecommunications services, whose negative correlation with the total demand is empirically measured in the literature through the price elasticity of demand. Unlike previous robust optimization works on the subject, we consider in this paper both sources of uncertainty and the correlation between them. The resulting mathematical model is a linear program that exhibits a constraint with quadratic dependency on the uncertainties. To solve the model, we propose a decomposition approach that avoids considering the constraint for all scenarios. Instead, we use a cutting plane algorithm that generates required scenarios on the fly by solving linear multiplicative programs. Computational experiments realized on the networks from SNDlib show that our approach is orders of magnitude faster than the classical semidefinite programming reformulation for such problems.

Keywords: Robust optimization; Network design; Random recourse; Linear multiplicative programming; Convex optimization

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 11/27/2014
Entry Accepted: 11/27/2014
Entry Last Modified: 11/27/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society