Optimization Online


A comparison of routing sets for robust network design

Michael Poss(mjposs***at***gmail.com)

Abstract: Designing a network able to route a set of non-simultaneous demand vectors is an important problem arising in telecommunications. The problem can be seen a two-stage robust program where the recourse function consists in choosing the routing for each demand vector. Allowing the routing to change arbitrarily as the demand varies yields a very difficult optimization problem so that different subsets of admissible routings have been discussed in the literature. In this paper, we compare theoretically the optimal capacity allocation costs for six of these routing sets: affine routing, volume routing and its two simplifications, the routing based on an arbitrary 2-cover of the uncertainty set, and the routing based on a cover delimited by a hyperplane. We show that the two routing sets based on covers of the uncertainty set yield the same optimal costs. We show then that the two simplified volume routings are special cases of affine routings. Finally, assuming that the uncertainty set is the one studied by Bertsimas and Sim (2004), we show that the optimal cost provided by volume routing is not less than the costs provided by the simplified volume routings.

Keywords: Robust optimization; Network design; Routing set; Routing template; Affine routing

Category 1: Network Optimization

Category 2: Robust Optimization

Citation: ULB, August 2011

Download: [PDF]

Entry Submitted: 09/01/2011
Entry Accepted: 09/01/2011
Entry Last Modified: 09/01/2011

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