NETWORK OPTIMIZATION BOOKS

Dimitri P. Bertsekas


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


  1. Introduction

    1. Graphs and Flows
      1. Paths and Cycles
      2. Flow and Divergence
      3. Path Flows and Conformal Decomposition
    2. Network Flow Models -- Examples
      1. The Minimum Cost Flow Problem
      2. Network Flow Problems with Convex Cost
      3. Multicommodity Flow Problems
      4. Discrete Network Optimization Problems
    3. Network Flow Algorithms -- An Overview
      1. Primal Cost Improvement
      2. Dual Cost Improvement
      3. Auction
      4. Good, Bad, and Polynomial Algorithms
    4. Notes and Sources

  2. Shortest Path Problems

    1. Problem Formulation and Applications
    2. A Generic Shortest Path Algorithm
    3. Label Setting (Dijkstra) Methods
      1. Performance of Label Setting Methods
      2. The Binary Heap Method
      3. Dial's Algorithm
    4. Label Correcting Methods
      1. The Bellman-Ford Method
      2. The D'Esopo-Pape Algorithm
      3. The SLF and LLL Algorithms
      4. The Threshold Algorithm
      5. Comparison of Label Setting and Label Correcting
    5. Single Origin/Single Destination Methods
      1. Label Setting
      2. Label Correcting
    6. Auction Algorithms
    7. Multiple Origin/Multiple Destination Methods
    8. Notes and Sources

  3. The Max-Flow Problem

    1. The Max-Flow and Min-Cut Problems
      1. Cuts in a Graph
      2. The Max-Flow/Min-Cut Theorem
      3. The Maximal and Minimal Saturated Cuts
      4. Decomposition of Infeasible Network Flow Problems
    2. The Ford-Fulkerson Algorithm
    3. Price-Based Augmenting Path Algorithms
      1. A Price-Based Path Construction Algorithm
      2. A Price-Based Max-Flow Algorithm
    4. Notes and Sources

  4. The Min-Cost Flow Problem

    1. Transformations and Equivalences
      1. Setting the Lower Flow Bounds to Zeros
      2. Eliminating the Upper Flow Bounds
      3. Reduction to a Circulation Format
      4. Reduction to an Assignment Problem
    2. Duality
      1. Interpretation of CS and the Dual Problem
      2. Duality and CS for Nonnegativity Constraints
    3. Notes and Sources

  5. Simplex Methods for Min-Cost Flow

    1. Main Ideas in Simplex Methods
      1. Using Prices to Obtain the In-Arc
      2. Obtaining the Out-Arc
      3. Dealing with Degeneracy
    2. The Basic Simplex Algorithm
      1. Termination Properties of the Simplex Method
      2. Initialization of the Simplex Method
    3. Extension to Problems with Upper and Lower Bounds
    4. Implementation Issues
    5. Notes and Sources

  6. Dual Ascent Methods for Min-Cost Flow

    1. Dual Ascent
    2. The Primal-Dual (Sequential Shortest Path) Method
    3. The Relaxation Method
    4. Sensitivity Analysis
    5. Implementation Issues
    6. Notes and Sources

  7. Auction Algorithms for Min-Cost Flow

    1. The Auction Algorithm for the Assignment Problem
      1. The Main Auction Algorithm
      2. The Approximate Coordinate Descent Interpretation
      3. Variants of the Auction Algorithm
      4. Computational Complexity -- $\e$-Scaling
      5. Dealing with Infeasibility
    2. Extensions of the Auction Algorithm
      1. Reverse Auction
      2. Auction Algorithms for Asymmetric Assignment
      3. Auction Algorithms with Similar Persons
    3. The Preflow-Push Algorithm for Max-Flow
      1. Analysis and Complexity
      2. Implementation Issues
      3. Relation to the Auction Algorithm
    4. The $\e$-Relaxation Method
      1. Computational Complexity -- $\e$-Scaling
      2. Implementation Issues
    5. The Auction/Sequential Shortest Path Algorithm
    6. Notes and Sources

  8. Nonlinear Network Optimization

    1. Separable Convex Problems Problems
    2. Multicommodity Flows
    3. Side Constraints
    4. Integer Constraints
    5. Networks with Gains
    6. Optimality Conditions
    7. Duality
    8. Algorithms and Approximations
      1. Feasible Direction Methods
      2. Piecewise Linear Approximation
      3. Interior Point Methods
      4. Penalty and Augmented Lagrangian Methods
      5. Proximal Minimization
      6. Smoothing
      7. Transformations
    9. Notes and Sources

  9. Convex Separable Network Problems

    1. Convex Functions of a Single Variable
    2. Optimality Conditions
    3. Duality
    4. Dual Function Differentiability
    5. Algorithms for Differentiable Dual Problems
    6. Auction Algorithms
      1. The $\e$-Relaxation Method
      2. The Auction/Sequential Shortest Path Algorithm
    7. Monotropic Programming
    8. Notes and Sources

  10. Network Problems with Integer Constraints

    1. Formulation of Integer-Constrained Problems
    2. Branch-and-Bound
    3. Lagrangian Relaxation
      1. Subgradient Optimization
      2. Cutting Planes
      3. Decomposition Methods for Multicommodity Flows
    4. Local Search Methods
      1. Tabu Search
      2. Genetic Algorithms
      3. Simulated Annealing
    5. Rollout Algorithms
    6. Notes and Sources

  11. References

  12. Index