An approach to robust network design in telecommunications

Georgios Petrou; Claude Lemaréchal; Adam Ouorou

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 4, page 411-426
  • ISSN: 0399-0559

Abstract

top
In telecommunications network design, one of the most frequent problems is to adjust the capacity on the links of the network in order to satisfy a set of requirements. In the past, these requirements were demands based on historical data and/or demographic predictions. Nowadays, because of new technology development and customer movement due to competitiveness, the demands present considerable variability. Thus, network robustness w.r.t demand uncertainty is now regarded as a major consideration. In this work, we propose a min-max-min formulation and a methodology to cope with this uncertainty. We model the uncertainty as the convex hull of certain scenarios and show that cutting plane methods can be applied to solve the underlying problems. We will compare Kelley, Elzinga-Moore and bundle methods.

How to cite

top

Petrou, Georgios, Lemaréchal, Claude, and Ouorou, Adam. "An approach to robust network design in telecommunications." RAIRO - Operations Research 41.4 (2007): 411-426. <http://eudml.org/doc/250130>.

@article{Petrou2007,
abstract = { In telecommunications network design, one of the most frequent problems is to adjust the capacity on the links of the network in order to satisfy a set of requirements. In the past, these requirements were demands based on historical data and/or demographic predictions. Nowadays, because of new technology development and customer movement due to competitiveness, the demands present considerable variability. Thus, network robustness w.r.t demand uncertainty is now regarded as a major consideration. In this work, we propose a min-max-min formulation and a methodology to cope with this uncertainty. We model the uncertainty as the convex hull of certain scenarios and show that cutting plane methods can be applied to solve the underlying problems. We will compare Kelley, Elzinga-Moore and bundle methods. },
author = {Petrou, Georgios, Lemaréchal, Claude, Ouorou, Adam},
journal = {RAIRO - Operations Research},
keywords = {Telecommunications network design; robust optimization; min-max-min problems; cutting plane methods; telecommunications network design; robust optimization},
language = {eng},
month = {10},
number = {4},
pages = {411-426},
publisher = {EDP Sciences},
title = {An approach to robust network design in telecommunications},
url = {http://eudml.org/doc/250130},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Petrou, Georgios
AU - Lemaréchal, Claude
AU - Ouorou, Adam
TI - An approach to robust network design in telecommunications
JO - RAIRO - Operations Research
DA - 2007/10//
PB - EDP Sciences
VL - 41
IS - 4
SP - 411
EP - 426
AB - In telecommunications network design, one of the most frequent problems is to adjust the capacity on the links of the network in order to satisfy a set of requirements. In the past, these requirements were demands based on historical data and/or demographic predictions. Nowadays, because of new technology development and customer movement due to competitiveness, the demands present considerable variability. Thus, network robustness w.r.t demand uncertainty is now regarded as a major consideration. In this work, we propose a min-max-min formulation and a methodology to cope with this uncertainty. We model the uncertainty as the convex hull of certain scenarios and show that cutting plane methods can be applied to solve the underlying problems. We will compare Kelley, Elzinga-Moore and bundle methods.
LA - eng
KW - Telecommunications network design; robust optimization; min-max-min problems; cutting plane methods; telecommunications network design; robust optimization
UR - http://eudml.org/doc/250130
ER -

References

top
  1. W. Ben-Ameur and H. Kerivin, Routing of uncertain traffic demands. Optim. Eng.3 (2005) 283–313.  
  2. A. Ben-Tal and A. Nemirovski, Robust convex optimization. Math. Oper. Res.23 (1998).  
  3. M. Bonatti, A. Gaivoronski, A. Lemonche and P. Polese, Summary of some traffic engineering studies carried out within RACE project R1044. European Transactions on Telecommunications5 (1994) 79–90.  
  4. O. Briant, C. Lemaréchal, Ph. Meurdesoif, S. Michel, N. Perrot and F. Vanderbeck, Technical Report 5453, Inria, 2005. Accepted for publication at Math. Program. 
  5. A.V. Demyanov, V.F. Demyanov and V.N. Malozemov, Minimaxmin problems revisited. Optim. Methods Softw.17 (2002) 783–804.  
  6. N.G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K.K. Ramakrishnan and J.E. van der Merwe, Resource managment with hoses: Point-to-cloud services for virtual private networks. IEEE/ACM Trans. Networking10 (2002) 679–692.  
  7. J. Elzinga and T.J. Moore, A central cutting plane algorithm for the convex programming problem. Math. Program.8 (1975) 134–145.  
  8. A. Frangioni, Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res.23 (1996) 1099–1118.  
  9. J.-L. Goffin, A. Haurie and J.-Ph. Vial, Decomposition and nondifferentiable optimization with the projective algorithm. Manage. Sci.38 (1992) 284–302.  
  10. J.L. Higle and S. Sen, Stochastic decomposition: An algorithm for two-stage linear programs with recourse. Math. Oper. Res.16 (1991) 650–669.  
  11. J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms. Springer-Verlag, Berlin (1993).  
  12. G.F. Italiano, S. Leonardi and G. Oriolo, Design of networks in the hose model, in 2nd International Workshop on Approximation and Randomization Algorithms in Communication Networks, Carleton Scientific Press (2002) 65–76.  
  13. J.E. Kelley, The cutting plane method for solving convex programs. J. Appl. Math. SIAM8 (1960) 703–712.  
  14. K. Kiwiel, Proximity control in bundle methods for convex nondifferentiable minimization. Math. Program.46 (1990) 105–122.  
  15. K. Kiwiel, A cholesky dual method for proximal piecewise linear programming. Numer. Math.68 (1994) 325–340.  
  16. P. Kouvelis and G. Yu, Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers (1997).  
  17. A. Kumar, R. Rastogi, A. Silberschatz and B. Yener, Algorithms for provisioning virtual private networks in the hose model. IEEE/ACM Trans. Networking10 (2002) 565–578.  
  18. C. Lemaréchal, Lagrangian relaxation, in Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions [based on a Spring School]2241, London, UK . Springer-Verlag (2001) 112–156.  
  19. A. Lisser, A. Ouorou, J.-Ph. Vial and J. Gondzio, Capacity planning under uncertain demand in telecommunication networks. Technical Report 99.13, Logilab, Department of Management Studies, University of Geneva, Switzerland, October 1999.  
  20. M. Lucertini and G. Paletta, A class of network design problems with multiple demand: Model formulation and an algorithmic approach. Math. Program. Stud.26 (1986) 225–228.  
  21. G.L. Nemhauser and W.B. Widhelm, A modified linear program for columnar methods in mathematical programming. Oper. Res.19 (1971) 1051–1060.  
  22. A. Ouorou, Robust capacity assignment in telecommunications. Comput. Manage. Sci.3 (2006) 285–305.  
  23. S. Sen, R.D. Doverspike and S. Cosares, Network planning with random demand. Telecommun. Syst.3 (1994) 11–30.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.