An approach to robust network design in telecommunications
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 4, pp. 411-426.

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.

DOI : 10.1051/ro:2007033
Classification : 65K05, 90C26, 90B12
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ro:2007033/

[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). | MR | Zbl

[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 Telecommunications 5 (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. | Zbl

[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. Networking 10 (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. | Zbl

[8] A. Frangioni, Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res. 23 (1996) 1099-1118. | Zbl

[9] J.-L. Goffin, A. Haurie and J.-Ph. Vial, Decomposition and nondifferentiable optimization with the projective algorithm. Manage. Sci. 38 (1992) 284-302. | Zbl

[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. | Zbl

[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. SIAM 8 (1960) 703-712. | Zbl

[14] K. Kiwiel, Proximity control in bundle methods for convex nondifferentiable minimization. Math. Program. 46 (1990) 105-122. | Zbl

[15] K. Kiwiel, A cholesky dual method for proximal piecewise linear programming. Numer. Math. 68 (1994) 325-340. | Zbl

[16] P. Kouvelis and G. Yu, Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers (1997). | MR | Zbl

[17] A. Kumar, R. Rastogi, A. Silberschatz and B. Yener, Algorithms for provisioning virtual private networks in the hose model. IEEE/ACM Trans. Networking 10 (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. | Zbl

[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. | Zbl

[21] G.L. Nemhauser and W.B. Widhelm, A modified linear program for columnar methods in mathematical programming. Oper. Res. 19 (1971) 1051-1060. | Zbl

[22] A. Ouorou, Robust capacity assignment in telecommunications. Comput. Manage. Sci. 3 (2006) 285-305. | Zbl

[23] S. Sen, R.D. Doverspike and S. Cosares, Network planning with random demand. Telecommun. Syst. 3 (1994) 11-30.

Cité par Sources :