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.
Mots-clés : telecommunications network design, robust optimization, min-max-min problems, cutting plane methods
@article{RO_2007__41_4_411_0,
author = {Petrou, Georgios and Lemar\'echal, Claude and Ouorou, Adam},
title = {An approach to robust network design in telecommunications},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {411--426},
publisher = {EDP-Sciences},
volume = {41},
number = {4},
year = {2007},
doi = {10.1051/ro:2007033},
mrnumber = {2361294},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2007033/}
}
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 - Recherche Opérationnelle PY - 2007 SP - 411 EP - 426 VL - 41 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2007033/ DO - 10.1051/ro:2007033 LA - en ID - RO_2007__41_4_411_0 ER -
%0 Journal Article %A Petrou, Georgios %A Lemaréchal, Claude %A Ouorou, Adam %T An approach to robust network design in telecommunications %J RAIRO - Operations Research - Recherche Opérationnelle %D 2007 %P 411-426 %V 41 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2007033/ %R 10.1051/ro:2007033 %G en %F RO_2007__41_4_411_0
Petrou, Georgios; Lemaréchal, Claude; Ouorou, Adam. An approach to robust network design in telecommunications. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 4, pp. 411-426. doi : 10.1051/ro:2007033. http://www.numdam.org/articles/10.1051/ro:2007033/
[1] and, Routing of uncertain traffic demands. Optim. Eng. 3 (2005) 283-313.
[2] and, Robust convex optimization. Math. Oper. Res. 23 (1998). | MR | Zbl
[3] ,, and, Summary of some traffic engineering studies carried out within RACE project R1044. European Transactions on Telecommunications 5 (1994) 79-90.
[4] ,,,, and, Technical Report 5453, Inria, 2005. Accepted for publication at Math. Program.
[5] , and, Minimaxmin problems revisited. Optim. Methods Softw. 17 (2002) 783-804. | Zbl
[6] ,,,, and, Resource managment with hoses: Point-to-cloud services for virtual private networks. IEEE/ACM Trans. Networking 10 (2002) 679-692.
[7] and, A central cutting plane algorithm for the convex programming problem. Math. Program. 8 (1975) 134-145. | Zbl
[8] , Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res. 23 (1996) 1099-1118. | Zbl
[9] , and, Decomposition and nondifferentiable optimization with the projective algorithm. Manage. Sci. 38 (1992) 284-302. | Zbl
[10] and, Stochastic decomposition: An algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16 (1991) 650-669. | Zbl
[11] and, Convex Analysis and Minimization Algorithms. Springer-Verlag, Berlin (1993).
[12] , and, 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] , The cutting plane method for solving convex programs. J. Appl. Math. SIAM 8 (1960) 703-712. | Zbl
[14] , Proximity control in bundle methods for convex nondifferentiable minimization. Math. Program. 46 (1990) 105-122. | Zbl
[15] , A cholesky dual method for proximal piecewise linear programming. Numer. Math. 68 (1994) 325-340. | Zbl
[16] and, Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers (1997). | MR | Zbl
[17] ,, and, Algorithms for provisioning virtual private networks in the hose model. IEEE/ACM Trans. Networking 10 (2002) 565-578.
[18] , 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. | Zbl
[19] ,, and, Capacity planning under uncertain demand in telecommunication networks. Technical Report 99.13, Logilab, Department of Management Studies, University of Geneva, Switzerland, October 1999.
[20] and, A class of network design problems with multiple demand: Model formulation and an algorithmic approach. Math. Program. Stud. 26 (1986) 225-228. | Zbl
[21] and, A modified linear program for columnar methods in mathematical programming. Oper. Res. 19 (1971) 1051-1060. | Zbl
[22] , Robust capacity assignment in telecommunications. Comput. Manage. Sci. 3 (2006) 285-305. | Zbl
[23] , and, Network planning with random demand. Telecommun. Syst. 3 (1994) 11-30.
Cité par Sources :
