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

@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}, publisher = {EDP-Sciences}, volume = {41}, number = {4}, year = {2007}, pages = {411-426}, doi = {10.1051/ro:2007033}, zbl = {pre05304963}, mrnumber = {2361294}, language = {en}, url = {http://www.numdam.org/item/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, Volume 41 (2007) no. 4, pp. 411-426. doi : 10.1051/ro:2007033. http://www.numdam.org/item/RO_2007__41_4_411_0/

[1] Routing of uncertain traffic demands. Optim. Eng. 3 (2005) 283-313.

and ,[2] Robust convex optimization. Math. Oper. Res. 23 (1998). | MR 1662410 | Zbl 0977.90052

and ,[3] Summary of some traffic engineering studies carried out within RACE project R1044. European Transactions on Telecommunications 5 (1994) 79-90.

, , and ,[4] Technical Report 5453, Inria, 2005. Accepted for publication at Math. Program.

, , , , and ,[5] Minimaxmin problems revisited. Optim. Methods Softw. 17 (2002) 783-804. | Zbl 1038.90095

, and ,[6] Resource managment with hoses: Point-to-cloud services for virtual private networks. IEEE/ACM Trans. Networking 10 (2002) 679-692.

, , , , and ,[7] A central cutting plane algorithm for the convex programming problem. Math. Program. 8 (1975) 134-145. | Zbl 0318.90048

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

,[9] Decomposition and nondifferentiable optimization with the projective algorithm. Manage. Sci. 38 (1992) 284-302. | Zbl 0762.90050

, and ,[10] Stochastic decomposition: An algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16 (1991) 650-669. | Zbl 0746.90045

and ,[11] Convex Analysis and Minimization Algorithms. Springer-Verlag, Berlin (1993).

and ,[12] 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.

, and ,[13] The cutting plane method for solving convex programs. J. Appl. Math. SIAM 8 (1960) 703-712. | Zbl 0098.12104

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

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

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

and ,[17] Algorithms for provisioning virtual private networks in the hose model. IEEE/ACM Trans. Networking 10 (2002) 565-578.

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

,[19] Capacity planning under uncertain demand in telecommunication networks. Technical Report 99.13, Logilab, Department of Management Studies, University of Geneva, Switzerland, October 1999.

, , and ,[20] 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

and ,[21] A modified linear program for columnar methods in mathematical programming. Oper. Res. 19 (1971) 1051-1060. | Zbl 0223.90018

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

,[23] Network planning with random demand. Telecommun. Syst. 3 (1994) 11-30.

, and ,