Belmont (Mass.): Athena Scientific, 1998. - 585 p.
An insightful, comprehensive, and up-to-date treatment of linear, nonlinear, and discrete/combinatorial network optimization problems, their applications, and their analytical and algorithmic methodology. It covers extensively theory, algorithms, and applications, and it aims to bridge the gap between linear and nonlinear network optimization on one hand, and integer/combinatorial network optimization on the other. Among its special features, the book: 1) provides a comprehensive account of the principal algorithms for linear network flow problems, including simplex, dual ascent, and auction algorithms 2) describes the application of network algorithms in many practical contexts, with special emphasis on data communication networks 3) develops in detail the computational complexity analysis of the main linear network optimization algorithms 4) covers extensively the main algorithms for specialized network problems, such as shortest path, max-flow, assignment, and traveling salesman 5) describes the main models for discrete network optimization problems, such as constrained shortest path, traveling salesman, vehicle routing, multidimensional assignment, facility location, spanning tree construction, etc 6) describes the main algorithmic approaches for integer-constrained network problems, such as branch-and-bound, Lagrangian relaxation and subgradient optimization, genetic algorithms, tabu search, simulated annealing, and rollout algorithms 7) develops the main methods for nonlinear network problems, such as convex separable and multicommodity flow problems arising in communication, transportation, and manufacturing contexts 8) discusses extensively auction algorithms, based on the author's original research on the subject 9) contains many examples, practical applications, illustrations, and exercises 10) contains much new material not found in any other textbook.
The book can be used for a course on network optimization or for part of a course on introductory optimization at the first-year graduate level. With the exception of some of the material in Chapter 9, the prerequisites are fairly elementary. The main one is a certain degree of mathematical maturity, as provided for example by a rigorous mathematics course beyond the calculus level.
The book contains a large number of examples and exercises, which should enhance its suitability for classroom instruction. Some of the exercises are theoretical in nature and supplement substantially the main text. Solutions to a subset of these (as well as errata and additional material)
will be posted and periodically updated on the book’s web page:
http://www.athenasc.com/netsbook.html
Also, the author’s web page:
http://web.mit.edu/dimitrib/www/home.html
contains listings of FORTRAN codes implementing many of the algorithms discussed in the book.
Contents:
Introduction.
Shortest Path Problems.
The Max-Flow Problem.
The Min-Cost Flow Problem.
Simplex Methods for Min-Cost Flow.
Dual Ascent Methods for Min-Cost Flow.
Auction Algorithms for Min-Cost Flow.
Nonlinear Network Optimization.
Convex Separable Network Problems.
Network Problems with Integer Constraints.
Appendix A: Mathematical Review.
References.
Index.