Handbook of Optimization in Telecommunications

Telecommunications has had a major impact in all aspects of life in the last century. There is little doubt that the transformation from the industrial age to the information age has been fundamentally influenced by advances in telecommunications.

Optimization problems are abundant in the telecommunications industry. The successful solution of these problems has played an important role in the development of telecommunications and its widespread use. Optimization problems arise in the design of telecommunication systems and in their operation.

The Handbook of Optimization in Telecommunications brings together experts from around the world who use optimization to solve problems that arise in telecommunications. The editors made an effort to cover recent optimization developments that are frequently applied to telecommunications. The spectrum of topics covered includes planning and design of telecommunication networks, routing, network protection, grooming, restoration, wireless communications, network location and assignment problems, Internet protocol, World Wide Web, and stochastic issues in telecommunications. The editors’ objective is to provide a reference tool for the increasing number of scientists and engineers in telecommunications who depend upon optimization in some way.

Each chapter in the handbook is of an expository nature, but of scholarly treatment, and includes a brief overview of the state-of-the-art thinking relative to the topic, as well as pointers to the key references in the field. Specialists as well as nonspecialists should find this handbook stimulating and helpful.

Preface Contributing Authors PART I. OPTIMIZATION ALGORITHMS 1. Interior point methods for large-scale linear programming (J.E. Mitchell, K. Farwell, and D. Ramsden) 2. Nonlinear programming in telecommunications (A. Migdalas) 3. Integer programming for telecommunications (E.K. Lee and D.P. Lewis) 4. Metaheuristics and applications to optimization problems in telecommunications (S.L. Martins and C.C. Ribeiro) 5. Lagrangian relax-and-cut algorithms (A. Lucena) 6. Minimum cost network ow algorithms (J. L. Kennington and R. V. Helgason) 7. Multicommodity network ow models and algorithms in telecommunications (M. Minoux) 8. Shortest path algorithms (P. Festa) PART II. PLANNING AND DESIGN 9. Network planning (H.P.L. Luna) 10. Multicommodity ow problems and decomposition in telecommunications networks (A. Lisser and Ph. Mahey) 11. Telecommunications network design (A. Forsgren and M. Prytz) 12. Ring network design (M. Henningsson, K. Holmberg, and D. Yuan) 13. Telecommunications access network design (T. Carpenter and H. Luss) 14. Optimization issues in distribution network design (G. R. Mateus and Z. K. G. Patrocínio Jr.) 15. Design of survivable networks (B. Fortz and M. Labbé) 16. Design of survivable networks based on p-cycles (W.D. Grover, J. Doucette, A. Kodian, D. Leung, A. Sack, M. Clouqueur, and G. Shen) 17. Optimization issues in quality of service (J.G. Klincewicz) 18. Steiner tree problems in telecommunications (S. Voß) 19. On formulations and methods for the hop-constrained minimum spanning tree problem (G. Dahl, L. Gouveia, and C.Requejo) 20. Location problems in telecommunications (D. Skorin-Kapov, J. Skorin-Kapov, and V. Boljuncic) 21. Pricing and equilibrium in communication networks (Q. Wang) PART III. ROUTING 22. Optimization of Dynamic Routing Networks (G. R. Ash) 23. ILP formulations for the routing and wavelength assignment problem: Symmetric systems (B. Jaumard, C. Meyer, and B. Thiongane) 24. Route optimization in IP networks (J. Rexford) 25. Optimization problems in multicast tree construction (C.A.S. Oliveira, P.M. Pardalos, and M.G.C. Resende) PART IV. RELIABILITY, RESTORATION, AND GROOMING 26. Network reliability optimization (A. Konak and A.E. Smith) 27. Stochastic optimization in telecommunications (A. A. Gaivoronski) 28. Network restoration (D. Medhi) 29. Telecommunication network grooming (R.S. Barr, M.S. Kingsley, and R.A. Patterson) PART V. WIRELESS 30. Graph domination, coloring and cliques in telecommunications (B. Balasundaram and S. Butenko) 31. Optimization in wireless networks (M. Min and A. Chinchuluun) 32. Optimization for planning cellular networks (E. Amaldi, A. Capone, F. Malucelli, and C. Mannino) 33. Load balancing in cellular wireless networks (S. Borst, G. Hampel, I. Saniee, and P. Whiting) PART VI. THE WEB AND BEYOND 34. Optimization issues in web search engines (Z. Liu and Ph. Nain) 35. Optimization in e-commerce (M. Kourgiantakis, I. Mandalianos, P.M. Pardalos, and A. Migdalas) 36. Optimization issues in combinatorial auctions (S. van Hoesel and R. Müller) 37. Supernetworks (A. Nagurney) Index