Optimization Online


Provisioning Virtual Private Networks under traffic uncertainty

A. Altin (aysegula***at***bilkent.edu.tr)
E. Amaldi (amaldi***at***elet.polimi.it)
P. Belotti (belotti***at***elet.polimi.it)
M. C. Pinar (mustafap***at***bilkent.edu.tr)

Abstract: We investigate a network design problem under traffic uncertainty which arises when provisioning Virtual Private Networks (VPNs): given a set of terminals that must communicate with one another, and a set of possible traffic matrices, sufficient capacity has to be reserved on the links of the large underlying public network so as to support all possible traffic matrices while minimizing the total reservation cost. The problem admits several variants depending on the desired topology of the reserved links, and the nature of the traffic data uncertainty. We present compact linear mixed-integer programming formulations for the problem with the classical hose traffic model and for a new, less conservative, robust variant relying on the traffic statistics that are often available. These flow-based formulations allow to solve optimally medium-to-large-size instances with commercial MIP solvers. We also propose a combined branch-and-price and cutting plane algorithm to tackle larger instances. Computational results obtained for several classes of instances are reported and discussed.

Keywords: Virtual private networks, network design, traffic uncertainty, robust optimization, linear mixed-integer programs, branch-and-price, cutting planes

Category 1: Network Optimization

Category 2: Robust Optimization

Category 3: Applications -- OR and Management Sciences (Telecommunications )

Citation: Technical Report n. 16, DEI, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133 Milano, Italy, January 2005.

Download: [PDF]

Entry Submitted: 02/25/2005
Entry Accepted: 02/25/2005
Entry Last Modified: 02/25/2005

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 Programming Society