NETWORK OPTIMIZATION BOOKS
Linear Network Optimization, MIT Press, 1991
The entire book, originally published by MIT Press, 1991, can be downloaded from here (260 pages, 1.8 Megs, format: .pdf). It focuses on the simplest/linear network flow problems (shortest path, max-flow, assignment, and single commodity min cost network flow). It describes the most popular algorithms, including primal simplex, primal-dual, relaxation/dual descent, and auction/epsilon-relaxation/preflow-push. The codes given in this book can be downloaded from elsewhere in this site (http://web.mit.edu/dimitrib/www/noc.htm).
Reviews:
"... gives an in-depth analysis of three basic techniques in network optimization which are applied to only a few of these problems, but leave the reader with a thorough understanding of the techniques. ... is perfect for a graduate class."
"The material presented includes the iterative shortest path algorithm and the relaxation method developed by Bertsekas and coauthors. In Chapter 4 the trend of focusing on results which have been developed by Bertsekas himself continues. I found this chapter the most interesting one, since it contains material from various papers by Bertsekas and coauthors nicely prepared for classroom use. The auction algorithm is first detailed for the assignment problem and then extended to the general minimum cost flow problem. Any lecturer who has chosen a different textbook for a course in network optimization should consider including parts of this chapter in her/his course."
H. W. Hamacher, in Math. Methods of Operations Research, Vol. 38, 1993
"... a very thorough treatise, starting from basics, on the theory and applications of the most common linear network optimization problems: shortest path, assignment, maximum flow, transportation and transshipment. Examples, illustrations and exercises are provided throughout the book."
"Professor Bertsekas' greater contribution in this book is the presentation of two algorithms he developed, "relaxation" and "auction," that allow extremely large (thousands of variables) problems of this type to be solved "routinely..."
J. A. Chisman, in IIE Transactions, Vol. 24, 1992
Contents and Preface,
Chapter 1, Introduction
Chapter 2, Simplex Methods
Chapter 3, Dual Ascent Methods
Chapter 4, Auction Algorithms
References
Network Optimization: Continuous and Discrete Models, Athena Scientific, 1998
Click to download the entire book (608 pages, format: .pdf).
The hardcopy book (ISBN
1-886529-02-7, 608 pages, hardcover) can be purchased from the publishing company, Athena Scientific.
This is a more extensive book than the 1991 book, and covers in addition to the simple linear models, problems involving nonlinear cost, multi-commodity flows, and integer constraints. One of its aims is to bridge the
gap between continuous and discrete/combinatorial network optimization.
Review:
"This beautifully written book provides an introductory treatment of linear, nonlinear, and discrete network
optimization problems... The textbook is addressed not only to students of optimization but to all scientists in
numerous disciplines who need network optimization methods to model and solve problems. This book is an engaging
read and it is highly recommended either as a textbook or as a reference on network optimization."
Panos Pardalos, University of Florida, in J. of Optimization Methods and
Sofware, 2000
Table of Contents: Network Optimization: Continuous and Discrete Models, Athena Scientific, 1998
Introduction
- Graphs and Flows
- Paths and Cycles
- Flow and Divergence
- Path Flows and Conformal Decomposition
- Network Flow Models -- Examples
- The Minimum Cost Flow Problem
- Network Flow Problems with Convex Cost
- Multicommodity Flow Problems
- Discrete Network Optimization Problems
- Network Flow Algorithms -- An Overview
- Primal Cost Improvement
- Dual Cost Improvement
- Auction
- Good, Bad, and Polynomial Algorithms
- Notes and Sources
Shortest Path Problems
- Problem Formulation and Applications
- A Generic Shortest Path Algorithm
- Label Setting (Dijkstra) Methods
- Performance of Label Setting Methods
- The Binary Heap Method
- Dial's Algorithm
- Label Correcting Methods
- The Bellman-Ford Method
- The D'Esopo-Pape Algorithm
- The SLF and LLL Algorithms
- The Threshold Algorithm
- Comparison of Label Setting and Label Correcting
- Single Origin/Single Destination Methods
- Label Setting
- Label Correcting
- Auction Algorithms
- Multiple Origin/Multiple Destination Methods
- Notes and Sources
The Max-Flow Problem
- The Max-Flow and Min-Cut Problems
- Cuts in a Graph
- The Max-Flow/Min-Cut Theorem
- The Maximal and Minimal Saturated Cuts
- Decomposition of Infeasible Network Flow Problems
- The Ford-Fulkerson Algorithm
- Price-Based Augmenting Path Algorithms
- A Price-Based Path Construction Algorithm
- A Price-Based Max-Flow Algorithm
- Notes and Sources
The Min-Cost Flow Problem
- Transformations and Equivalences
- Setting the Lower Flow Bounds to Zeros
- Eliminating the Upper Flow Bounds
- Reduction to a Circulation Format
- Reduction to an Assignment Problem
- Duality
- Interpretation of CS and the Dual Problem
- Duality and CS for Nonnegativity Constraints
- Notes and Sources
Simplex Methods for Min-Cost Flow
- Main Ideas in Simplex Methods
- Using Prices to Obtain the In-Arc
- Obtaining the Out-Arc
- Dealing with Degeneracy
- The Basic Simplex Algorithm
- Termination Properties of the Simplex Method
- Initialization of the Simplex Method
- Extension to Problems with Upper and Lower Bounds
- Implementation Issues
- Notes and Sources
Dual Ascent Methods for Min-Cost
Flow
- Dual Ascent
- The Primal-Dual (Sequential Shortest Path) Method
- The Relaxation Method
- Sensitivity Analysis
- Implementation Issues
- Notes and Sources
Auction Algorithms for Min-Cost Flow
- The Auction Algorithm for the Assignment Problem
- The Main Auction Algorithm
- The Approximate Coordinate Descent Interpretation
- Variants of the Auction Algorithm
- Computational Complexity -- $\e$-Scaling
- Dealing with Infeasibility
- Extensions of the Auction Algorithm
- Reverse Auction
- Auction Algorithms for Asymmetric Assignment
- Auction Algorithms with Similar Persons
- The Preflow-Push Algorithm for Max-Flow
- Analysis and Complexity
- Implementation Issues
- Relation to the
Auction Algorithm
- The $\e$-Relaxation Method
- Computational Complexity -- $\e$-Scaling
- Implementation Issues
- The Auction/Sequential Shortest Path Algorithm
- Notes and Sources
Nonlinear Network Optimization
- Separable Convex Problems Problems
- Multicommodity Flows
- Side Constraints
- Integer Constraints
- Networks with Gains
- Optimality Conditions
- Duality
- Algorithms and Approximations
- Feasible Direction Methods
- Piecewise Linear Approximation
- Interior Point Methods
- Penalty and Augmented Lagrangian Methods
- Proximal Minimization
- Smoothing
- Transformations
- Notes and Sources
Convex Separable Network Problems
- Convex Functions of a Single Variable
- Optimality Conditions
- Duality
- Dual Function Differentiability
- Algorithms for Differentiable Dual Problems
- Auction Algorithms
- The $\e$-Relaxation Method
- The Auction/Sequential Shortest Path Algorithm
- Monotropic Programming
- Notes and Sources
Network Problems with Integer
Constraints
- Formulation of Integer-Constrained Problems
- Branch-and-Bound
- Lagrangian Relaxation
- Subgradient Optimization
- Cutting Planes
- Decomposition Methods for Multicommodity Flows
- Local Search Methods
- Tabu Search
- Genetic Algorithms
- Simulated Annealing
- Rollout Algorithms
- Notes and Sources
References
Index