NETWORK MODELS
Edited by M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser
PREFACE
Networks pervade everyday life in a modern technological society. When we travel to work or to a place to shop, we do so over a transportation network. When we make a telephone call or watch television, we receive electronic signals delivered to us through a telecommunications network. When we try to advance our careers, we must deal with the vagaries of social networks. This handbook considers the scientific analysis of network models. It covers methodology, algorithms, and computer implementations, and a variety of network models used extensively by business and government to design and manage the networks they encounter each day.
Network models have played a key role in the development of operations research and management science since the initial development of these disciplines. Network flow theory developed alongside the theory of linear programming. Network models have been the basis for many of the fundamental developments in integer programming. Early on, researchers recognized that network flow problems define a class of linear programs that always have integer extreme point optimal solutions. Attempts to understand and generalize this finding led to many new results, culminating in an entire branch of optimization known as polyhedral combinatorics. Work on the matching problem was fundamental to the development of both combinatorial optimization and complexity theory. The traveling salesman problem has served as the prototypical problem for nearly all developments in integer programming and combinatorial optimization. The development of fast network flow codes spurred the development of strong interactions between operations research and computer science and the application of optimization models in a wide range of industries.
The set of papers in this Handbook reflect both the rich theory and wide range of applications of network models. Two of the most vibrant applications areas of network models are telecommunications and transportation. Several chapters explicitly model issues arising in these problem domains. Research on network models has been closely aligned with the field of computer science both in developing data structures for efficiently implementing network algorithms and in analyzing the complexity of network problems and algorithms. The basic structure underlying all network problems is a graph. Thus, there has historically been strong ties between network models and graph theory. The papers contained in this volume reflect these various relationships.
The first four chapters treat core network models and applications. Chapter 1 by Ahuja, Magnanti, Orlin and Reddy describes a variety of network applications. The diversity of the problems discussed in this chapter shows why practitioners and researchers have applied network models so extensively in practice. The field of network optimization is most commonly associated with the minimum cost flow problem and with several of its classical specializations: the shortest path problem the maximum flow problem and the transportation problem. The first volume in this series, the Handbook on Optimization, covers the fundamentals of network flows. Chapter 2 of this volume, by Helgason and Kennington, analyzes alternate approaches for implementing network flow algorithms and direct generalizations of the network flow problem. Analysts have used these techniques to develop highly efficient codes for network flows, generalized network flows and related problems. The matching problem and the traveling salesman problem are two network optimization problems that in many ways set the stage for all combinatorial optimization problems. Chapter 3 treats the matching problem. The polynomial time solution algorithm for this problem exploits both the structure of the underlying polyhedron as well as the problem's special graphical properties. The traveling salesman problem has served as the development ground and testbed for the entire range of techniques for difficult (i.e., NP-hard) combinatorial optimization problems. Chapter 4 by Junger, Reinelt and Rinaldi reviews a variety of approaches, while concentrating on those that have been shown to be effective at solving problems of practical size.
The second group of papers present recent fundamental advances in network algorithms. Significant advances in hardware architectures for computationally intensive operations are likely to increasingly involve parallel computing. Chapter 5 by Bertsekas, Castanon, Eckstein and Zenios treats the design and analysis of parallel algorithms for network optimization. A second important general trend in computer science is probabilistic algorithms and probabilistic analysis of algorithms. Chapter 6 by Steele and Snyder treats these topics. During the past few years, and in many problem settings, researchers have recognized the possibility of designing more efficient algorithms for certain problems by directly modeling and exploiting the underlying geometric problem structure. Chapter 7 by Mitchell and Suri covers this topic. One of the most significant developments in combinatorics in the past ten years is the Graph Minor Project due to Robertson, Seymour and Thomas. In Chapter 8, Bienstock and Langston discuss the extensive implications of this body of work.
The next two chapters cover methodology for constructing networks with certain properties. Much of this work is motivated by telecommunications network design problems. Chapter 9, by Magnanti and Wolsey, addresses the problem of designing tree networks. This class of problems includes a problem fundamental to both network optimization and matroid optimization, the minimum spanning tree problem and several of its variants and extensions. In several applications, networks must be able to withstand the failure/deletion of a single arc. This requirement leads to survivable network design problems which Grotschel, Monma and Stoer treat in Chapter 10. Once a network is constructed, we often wish to compute a measure of its reliability given the reliability (probability of operation) of its components. Chapter 11 by Ball, Colbourn and Provan covers these reliability analysis problems.
A companion volume in the Handbook series, entitled Network Routing, examines problems related to the movement of commodities over a network. The problems treated arise in several application areas including logistics, telecommunications, facility location, VI-SI design, and economics.
The broad set of material covered in both these volumes attests to the richness of networks as both a significant scientific field of inquiry and as an important pragmatic modeling and problem solving tool. In this sense, networks is a problem domain that reflects the best tradition of operations research and management science and allied fields such as applied mathematics and computer science. We hope that the set of papers assembled in this volume will serve as a valuable summary and synthesis of the extensive network literature and that this material might inspire its readers to develop additional theory and practice that builds upon this fine tradition.
Michael Ball
Tom Magnanti
Clyde Monma
George Nemhauser
Complete chapters on ScienceDirect
[Description and order information]
Home | Elsevier Sites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company