An approach to robust network design in telecommunications
RAIRO - Operations Research - Recherche Opérationnelle, Volume 41 (2007) no. 4, p. 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.

Classification:  65K05,  90C26,  90B12
Keywords: telecommunications network design, robust optimization, min-max-min problems, cutting plane methods
     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},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {4},
     year = {2007},
     pages = {411-426},
     doi = {10.1051/ro:2007033},
     zbl = {pre05304963},
     mrnumber = {2361294},
     language = {en},
     url = {}
Petrou, Georgios; Lemaréchal, Claude; Ouorou, Adam. An approach to robust network design in telecommunications. RAIRO - Operations Research - Recherche Opérationnelle, Volume 41 (2007) no. 4, pp. 411-426. doi : 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 1662410 | Zbl 0977.90052

[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 1038.90095

[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 0318.90048

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

[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 0762.90050

[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 0746.90045

[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 0098.12104

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

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

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

[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 1052.90065

[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 0586.90032

[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 0223.90018

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

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