Network Optimization: Continuous and Discrete Models

Dimitri P. Bertsekas

Click to download four chapters (1, 2, 3, 10), the preface, and the references (270 pages, 1.1 Megs, format: .pdf).

The complete book (ISBN 1-886529-02-7, 608 pages, hardcover) can be purchased from the publishing company, Athena Scientific.

The purpose of the book is to provide 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.

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

Network Optimization: Continuous and Discrete Models

  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