Handbook of Optimization in Telecommunications

We discuss interior point methods for large-scale linear programming, with an emphasis on methods that are useful for problems arising in telecommunications. We give the basic framework of a primal-dual interior point method, and consider the numerical issues involved in calculating the search direction in each iteration, including the use of factorization methods and/or preconditioned conjugate gradient methods. We also look at interior point column generation methods which can be used for very large scale linear programs or for problems where the data is generated only as needed.

Telecommunications have always been the subject of application for advanced mathematical techniques. In this chapter, we review classical nonlinear programming approaches to modeling and solving certain problems in telecommunications. We emphasize the common aspects of telecommunications and road networks, and indicate that several lessons are to be learned from the field of transportation science, where game theoretic and equilibrium approaches have been studied for more than forty years. Several research directions are also stated.

This chapter presents an overview of integer programming in the field of telecommunications. Various integer programming models are described, and computational strategies for solving the integer programming instances are summarized. Techniques such as branching variable selection and node selection schemes are discussed; and the concepts of problem preprocessing and reformulation, heuristics, and continuous reduced-cost fixing are outlined. These latter techniques have been shown to be very effective when embedded within a branch-and-bound algorithm. The use of an interior point method as a subproblem solver is also described. Finally, Lagrangian relaxation in the context of solving specific telecommunication instances is analyzed as an alternative relaxation for use within the branch-and-bound tree search environment.

Recent years have witnessed huge advances in computer technology and communication networks, entailing hard optimization problems in areas such as network design and routing. Metaheuristics are general high-level procedures that coordinate simple heuristics and rules to find good approximate solutions to computationally difficult combinatorial optimization problems. Among them, we find simulated annealing, tabu search, GRASP, VNS, genetic algorithms, and others. They are some of the most effective solution strategies for solving optimization problems in practice and have been applied to a very large variety of problems in telecommunications. In this chapter, we review the main components that are common to different metaheuristics. We also describe the main principles associated with several metaheuristic and we give templates for basic implementations of them. Finally, we present an account of some successful applications of metaheuristics to optimization problems in telecommunications.

Attempts to allow exponentially many inequalities to be candidates to Lagrangian dualization date from the early 1980s. In the literature, the term

Relax-and-Cut

is being used to denote the whole class of Lagrangian Relaxation algorithms where Lagrangian bounds are attempted to be improved by dynamically strengthening relaxations with the introduction of valid constraints (possibly selected from families with exponentially many constraints). In this chapter, Relax-and-Cut algorithms are reviewed in their two flavors. Additionally, a general framework to obtain feasible integral solutions (that benefit from Lagrangian bounds) is also presented. Finally, the use of Relax-and-Cut is demonstrated through an application to a

hard-to-solve

instance of the Knapsack Problem. For that application, Gomory cuts are used, for the first time, within a Lagrangian relaxation framework.

The minimal cost network flow model is defined along with optimality criteria and three efficient procedures for obtaining an optimal solution. Primal and dual network simplex methods are specializations of well-known algorithms for linear programs. The primal procedure maintains primal feasibility at each iteration and seeks to simultaneously achieve dual feasibility, The dual procedure maintains dual feasibility and moves toward primal feasibility. All operations for both algorithms can be performed on a graphical structure called a tree. The scaling push-relabel method is designed exclusively for optimization problems on a network. Neither primal nor dual feasibility is achieved until the final iteration.

We present an overview of mathematical optimization models and solution algorithms related to optimal network design and dimensioning in telecommunications. All the models discussed are expressed in terras of minimum cost multicommodity network flows with appropriate choice of link (or node) cost functions. Various special cases related to practical applications are examined, including the linear case, the linear with fixed cost case, and the case of general discontinuous nondecreasing cost functions. It is also shown how the generic models presented can accommodate a variety of constraints frequently encountered in applications, such as, among others, constraints on the choice of routes, robustness and survivability constraints. Finally we provide an overview of recent developments in solution algorithms, emphasizing those approaches capable of finding provably exact solutions, which are essentially based on general mixed integer programming techniques, relaxation, cutting-plane generation techniques and branch & cut.

Shortest path problems are fundamental network optimization problems arising in many contexts and having a wide range of applications, including dynamic programming, project management, knapsack problems, routing in data networks, and transportation problems. The scope of this chapter is to provide an extensive treatment of shortest path algorithms covering both classical and recently proposed approaches.

This chapter describes the main results of two decades of experience in studying and applying optimization models in the telecommunications sector. The Brazilian information technology policy has enabled during this time many fruitful contracts among some universities and companies of the sector, and the author with some colleagues have been engaged in this process with emphasis in the use of operations research (OR) methods. The author has also been benefited from the cooperation with French institutions that have similar engagements in that country, in such a way that the chapter is in part grounded in real case studies that have motivated research and development of different decision support systems. The chapter synthesize the framework that has been used to integrate models of local access and backbone networks, and then presents a past and future perspective on how is progressing the use of OR models to address the important questions of routing, planning and pricing services in telecommunication and computer networks. Most of the applications are related to the literature and have universal character, but we try to point out in this experience how different cultures, geography and politics impact and shape the way operations research is practiced around the world.

The purpose of this chapter is to investigate multicommodity flow problems that appear in the network design and operation of modern broadband packet-switched networks. We present arc-node and arc-path models and analyze specialized formulations corresponding to hard to solve instances like the minimax congestion problem and the capacity assignment of data networks in the presence of failures. Decomposition methods are studied to cope with the coupling constraints which define interactions between commodities on critical arcs or the combinatorial choice between normal and spare capacities. We focus here mainly on continuous flow models with linear or convex costs.

Telecommunications networks are fundamental in any telecommunications system. The network has to meet a number of criteria for the performance to be satisfactory. Hence, when designing the network, one may pose a number of optimization problems whose solutions give networks that are, in some sense, optimally designed. As the networks have become increasingly complex, the aid of optimization techniques has also become increasingly important. This is a vast area, and this chapter considers an overview of the issues that arise as well as a number of specific optimization models and problems. Often the problems may be formulated as mixed-integer linear programs. Due to problem size and problem structure, in many cases specially tailored solution techniques need to be used in order to solve, or approximately solve, the problems.

Applying traditional methods of network design on modern telecommunication data often results in tree-like structures, due to the high capacities of the current optical fibers. However, the increasing importance of the traffic on telecommunication networks makes the issue of survivability more crucial. It is not acceptable that parts of the network are completely unable to communicate if a single link failure should occur. Therefore telecommunication networks must be designed so that certain survivability requirements are fulfilled. In this chapter we study the case where the survivability requirement is that the network should be composed of connected rings of links. In case of a failure in a ring, the traffic can simply be sent the other way around the ring. We describe a solution approach iteratively generating rings in a meaningful way, as the number of possible rings is very large. A model deciding the optimal usage of a given set of rings and a model generating valid rings are used together, to form a method of column generation-type. We also review work on other types of ring network design problems.

A typical telecommunications network consists of a backbone network and multiple access networks. The investment in expanding and modernizing the access portion of the network is a significant part of the total. This chapter concentrates on describing representative models and solution approaches that are often found in access network design. Section 13.2 presents variations of concentrator location problems that play a major part in access network design. Section 13.3 focuses on current broadband access networks that deliver information at high speed, such as access networks that employ Digital Subscriber Line (DSL) and cable TV technologies. Finally, Section 13.4 describes the design of survivable access networks; in particular, access networks with dual homing and access networks that employ ring topologies.

A distribution network design problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. Improvements of technologies used to deploy distribution networks have contributed to make distribution network planning more similar to other levels of access network. The major points that differentiate distribution network design problems are its huge dimensions and the several technological options that could be used to connect customers. Major technological trends to deploy distribution networks are discussed here. As an extension of the capacitated network design problem, it is a NP-hard combinatorial optimization problem. The need to install facilities and capacities in discrete levels and the incorporation of addition technology-related cost terms and constraints makes the exact solution of the mixed integer programming model even harder. There are several models and strategies that might be devised for solving those models, we present some of them.

Long-term planning of backbone telephone networks has been an important area of application of combinatorial optimization over the last few years. In this chapter, we review polyhedral results for models related to these problems. In particular, we study classical survivability requirements in terms of

k

-connectivity of the network, then we extend the survivability model to include the notion of

bounded rings

that limit the length of the rerouting path in case of link failure.

p

-Cycles are a recently discovered and promising new paradigm for surviv-able networking.

p

-Cycles simultaneously provide the switching speed and simplicity of rings with the much greater capacity-efficiency and flexibility for reconfiguration of a mesh network.

p

-Cycles also permit shortest-path routing of working paths (as opposed to ring-constrained working path routing), which adds further to network capacity efficiency. Operationally

p

-cycles are similar to BLSRs in that, upon failure, switching actions are required at only two nodes and both those nodes are fully pre-planned as to the actions that are required for any failure detected at their sites. With the optimization models in this chapter, entire survivable transport networks can be easily designed with essentially the same spare to working capacity (redundancy) ratios as optimized span-restorable mesh networks.

p

-Cycles thus bridge the ring versus mesh debate that dominated work in survivable networks through the 1990s and provide the best of both worlds:

the efficiency of mesh with the speed of rings

.

The advent of the World Wide Web has fundamentally changed the nature of Internet traffic. New classes of applications, such as video conferencing, Internet telephony and various forms of e-commerce have arisen, for which so-called

best effort

service is no longer acceptable. These new applications represent delay-sensitive traffic with specific performance requirements. The term Quality of Service (QoS) is used to describe network features that are designed to provide the better than

best effort

performance that is required by such applications. In this chapter, we consider QoS in the context of network design. Specifically, we focus on network design or optimization problems that address link topology, link capacity, route assignment and/or router location, and that take various performance requirements into account. In particular, solutions to these network design problems ensure that sufficient resources (e.g., bandwidth) are made available so that certain specified performance requirements (e.g., delay requirements) will be explicitly met.

Connecting a given set of points at minimum cost may be rated as one of the most important problems in telecommunications network design. Related questions may be formulated in metric spaces as well as in graphs. Given a weighted graph, the

Steiner tree problem in graphs

asks to determine a minimum cost subgraph spanning a set of specified vertices. This problem may be viewed as

the

combinatorial optimization problem in telecommunications. In this chapter, we survey Steiner problems from a telecommunications perspective with a special emphasis on the problem in graphs.

In this chapter we present a general framework for modeling the hopconstrained minimum spanning tree problem (HMST) which includes formulations already presented in the literature. We present and survey different ways of computing a lower bound on the optimal value. These include, Lagrangian relaxation, column generation and model reformulation. We also give computational results involving instances with 40 and 80 nodes in order to compare some of the ideas discussed in the chapter.

Location optimization is an important problem in design and usage of telecommunication networks. In different forms it appears in wire-based and in wireless networks, during unicast and multicast usage, in static, as well as in dynamic, networks. We provide an application oriented survey of recent results in location optimization pertaining to telecommunications networks, addressing problems such as converter, splitter, and amplifier placement in wavelength division multiplex (WDM) optical networks, concentrator location in designing access/backbone networks, base station location in Universal Mobile Telecommunication System (UMTS), and location management in mobile (cellular and ad hoc) networks.

Combine pricing and engineering in communication networks improves resources management to a great extent, and optimization models provide a bridge between the two disciplines. In this chapter, we survey a set of network pricing models. Managing network resources involves decision-making at many levels. Correspondingly, our survey takes a “divide and review” approach that classifies various pricing models into three categories: models that support on-line resources allocation; models that assist offline bandwidth provisioning; and models that complement long-term capacity planning. In discussing pricing schemes in each category, we highlight economic thinking behind model formulation, specific issues to be resolved by both pricing and engineering, and important insights obtained from the optimization results.

This chapter describes optimization methods useful for the design of dynamic routing protocols, as well as for the concomitant optimization of dynamic routing network design and dynamic routing performance. A variety of dynamic routing methods are used in practice, which include time-dependent, state-dependent, and event-dependent algorithms, and these are briefly outlined. We briefly review current practice in dynamic routing protocol design in voice, data, and integrated voice/data networks. Case studies are given for dynamic routing protocol design for a) real-time network routing, a state-dependent dynamic routing method used in practice in a very large-scale application, and b) integrated voice/data routing in an IP/MPLS network application. Methods for optimal min-cost network design and max-flow performance optimization include traffic-load-flow, discrete-event flow, and virtual-transport-flow optimization models. Examples are given in the application of these methods.

Different integer linear programming (ILP) formulations have been proposed for the routing and wavelength assignment problem in WDM optical networks, mainly for asymmetrical systems, more than for symmetrical systems, under different objectives. We propose a synthesis of the mathematical models for symmetrical systems, with a unified and simplified notation for four widely used objectives. As for asymmetrical traffic models (Jaumard, Meyer, and Thiongane, 2004), we show that all formulations, both link and path formulations, are equivalent in terms of the upper bound value provided by the optimal solution of their linear programming relaxation, although their number of variables and constraints differ. We propose an experimental comparison of the best linear relaxation bounds with the optimal ILP solutions whenever it is possible, for several network and traffic instances.

The performance and reliability of the Internet depend, in large part, on the operation of the underlying routing protocols. Today’s IP routing protocols compute paths based on the network topology and configuration parameters, without regard to the current traffic load on the routers and links. The responsibility for adapting the paths to the prevailing traffic falls to the network operators and management systems. This chapter discusses the modeling and computational challenges of optimizing the tunable parameters, starting with conventional intradomain routing protocols that compute shortest paths as the sum of configurable link weights. Then, we consider the problem of optimizing the interdomain routing policies that control the flow of traffic from one network to another. Optimization based on local search has proven quite effective in grappling with the complexity of the routing protocols and the diversity of the performance objectives, and tools based on local search are in wide use in today’s large IP networks.

Multicasting is a technique for data routing in networks that allows multiple destinations to be addressed simultaneously. The implementation of multicasting requires, however, the solution of difficult combinatorial optimization problems. In this chapter, we discuss combinatorial issues occurring in the implementation of multicast routing, including multicast tree construction, minimization of the total message delay, center-based routing, and multicast message packing. Optimization methods for these problems are discussed and the corresponding literature reviewed. Mathematical programming as well as graph models for these problems are discussed.

This chapter presents design of reliable networks. The exact calculation of any general network reliability measure is NP-hard. Therefore, network designers have been reluctant to use reliability as a design criterion. However, reliability is becoming an important concern to provide continuous service quality to network customers. The chapter discusses various network reliability measures and efficient techniques to evaluate them. Two genetic algorithms are presented to demonstrate how these techniques to estimate and compute network reliability can be incorporated within an optimization algorithm. Computational experiments show that the proposed approaches significantly reduce computational effort without compromising design quality.

We survey different optimization problems under uncertainty which arise in telecommunications. Three levels of decisions are distinguished: design of structural elements of telecommunication networks, top level design of telecommunication networks, and design of optimal policies of telecommunication enterprise. Examples of typical problems from each level show that the stochastic programming paradigm is a powerful approach for solving telecommunication design problems.

An important problem in the design and deployment of communication networks is the issue of network restoration to address for various types of failures. In this chapter, we consider a variety of networks and networking technologies and argue that networks can be broadly classified as either traffic networks or transport networks. We then present optimization models for network protection for link failures and discuss how they fit into this classification. We then discuss the process of network restoration and interaction between the traffic and the transport network. Finally, we also discuss situations and failures for which restoration is difficult to model—an area that requires further exploration.

Grooming has emerged as an active area of research within the operations research and telecommunications fields and concerns the optimization of network transmissions that span multiple distinct transmission channels, protocols, or technologies. This chapter explores the meaning of grooming, the technical context in which it can be applied, and example situations. A new taxonomy captures key aspects of grooming problems and is used to summarize over 50 key publications on this important traffic-engineering and optimization problem class.

This chapter aims to provide a detailed survey of existing graph models and algorithms for important problems that arise in different areas of wireless telecommunication. In particular, applications of graph optimization problems such as minimum dominating set, minimum vertex coloring and maximum clique in multihop wireless networks are discussed. Different forms of graph domination have been used extensively to model clustering in wireless ad hoc networks. Graph coloring problems and their variants have been used to model channel assignment and scheduling type problems in wireless networks. Cliques are used to derive bounds on chromatic number, and are used in models of traffic flow, resource allocation, interference, etc. In this chapter we survey the solution methods proposed in the literature for these problems and some recent theoretical results that are relevant to this area of research in wireless networks.

Wireless ad hoc networks consist of autonomous nodes and require each node’s cooperation in communications. Since the network environment does not assume any infrastructure, communication tasks are performed in an ad-hoc fashion and many well-established protocols for wired networks are not applicable in such a network. In this chapter, we survey several combinatorial optimization. problems in wireless ad hoc networks and discuss applications of the problems. To improve the solution quality, the intrinsic natures of wireless communications should be considered in designing algorithms.

During the last decade the tremendous success of mobile phone systems has triggered considerable technological advances as well as the investigation of mathematical models and optimization algorithms to support planning and management decisions. In this chapter, we give an overview of some of the most significant optimization problems arising in planning second and third generation cellular networks, we describe the main corresponding mathematical models, and we briefly mention some of the computational approaches that have been devised to tackle them. For second generation systems (GSM), the planning problem can be subdivided into two distinct subproblems: coverage planning, in which the antennas are located so as to maximize service coverage, and capacity planning, in which frequencies are assigned to the antennas so as to maximize a measure of the overall quality of the received signals. For third generation systems (UMTS) network planning is even more challenging, since, due to the peculiarities of the radio interface, coverage and capacity issues must be simultaneously addressed.

We present a linear-programming approach for dynamic load balancing in CDMA networks. The linear program characterizes the minimum achievable base station load for a given configuration of mobiles at each time interval, and gives a useful benchmark for the potential gains from optimizing the power assignment. The solution of the linear program also offers valuable insight to the qualitative properties of the optimal power allocation. In particular, the structure of the optimal assignment reflects the critical notion that power allocation should not just be based on signal strength values but also on shadow prices which arise from load considerations. We develop a dual-ascent scheme for solving the linear program in a (mostly) distributed fashion with low communication overhead. Extensive numerical experiments demonstrate that there is scope for significant gains from balancing base station loads in typical scenarios.

Crawlers are deployed by a Web search engine for collecting information from different Web servers in order to maintain the currency of its data base of Web pages. We present studies on the optimization of Web search engines from different perspectives. We first investigate the number of crawlers to be used by a search engine so as to maximize the currency of the data base without putting an unnecessary load on the network. Both the static setting, where crawlers are always active, and the dynamic setting where, crawlers may be activated/deactivated as a function of the state of the system, are addressed. We then consider the optimal scheduling of the visits of these crawlers to the Web pages assuming these pages are modified at different rates. Finally, we briefly discuss some other optimization issues of Web search engines, including page ranking and system optimization.

This chapter explores the relative literature of and provides a reference tool for optimization and game theory in e-commerce. Moreover, in order to satisfy a broad range of readers, a brief overview is given in several e-business issues. Beside its horizontal character, this chapter presents some of the most up to date applications of operations research, game theory, and mathematical programming modeling techniques to four basic issues in e-business: e-supply chain, e-auctions, data mining and the “cost and pricing” problem in the Internet. Several opportunities for future research are also presented.

Auctions are used more and more to sell a large variety of goods. In this chapter, it is our objective to concentrate on applications of auctions in telecommunication, which possess a part or a feature that can be optimized. Optimization methods are necessary, in particular, when auctions are used to sell or purchase goods which consist of combinations of items, and where combinations have higher or lower value than the sum of values of individual items: combinatorial auctions. In the first part, we review the theory on combinatorial auctions, starting with the various properties and mechanisms found in the literature on combinatorial auctions. Then the allocation decision is identified as the winner determination problem (WDP), which is the central subject of this chapter. The winner determination problem is formulated as an Integer Linear Program (ILP) with the structure of a set-packing problem. Therefore, complexity results, polynomial special cases, and general solution methods for the WDP are often obtained from results for the set-packing problem. In the second part of this chapter, we turn to applications from telecommunications. First, a model for bandwidth allocation in networks is discussed. The problem is translated into a formulation that has close relations to multi-commodity flow and network synthesis. This guides us to alternative formulations and to solution methods. Second, the auctions of radio spectrum in the US and Europe are reviewed. The WDP of these multi-round auctions can be modeled using the XOR-of-OR bidding language, and solved by methods originally developed for set-packing.

This chapter describes supernetworks as a formalism for the modeling and analysis of complex decision-making in the Information Age, which is characterized by the prominent role played by telecommunication networks coupled with other networks. The chapter traces the concept and term, whose origins lie in transportation science and computer science, and lays its foundations in the context of system-optimization versus user-optimization. The Braess paradox is recalled and its relevance to network design discussed. Multicriteria supernetworks are subsequently modeled and variational inequality formulations of the governing equilibrium conditions given, along with an explicit application to telecommuting versus commuting decision-making. Both multitiered as well as multilevel supernetworks are highlighted and a plethora of applications such as supply chains with electronic commerce, integrated social and supply chain networks, and financial networks with intermediation and electronic transactions are overviewed.