Skip to Content
Report an accessibility problem
Engineering  |  Dimitri Bertsekas

Network optimization – auction algorithms

Network Optimization: Continuous and Discrete Models, Athena Scientific, 1998

This is an extensive book on network optimization theory and algorithms, 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.

Click here to download the entire book in .pdf format.

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

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

Linear Network Optimization, MIT Press, 1991

 

The entire book, originally published by MIT Press, 1991, can be downloaded from here. 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 (https://live-dimitri-bertsekas.pantheonsite.io/network-optimization-codes).

 

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 PrefaceChapter 1, Introduction, Chapter 2, Simplex Methods, Chapter 3, Dual Ascent Methods, Chapter 4, Auction Algorithms, References

 

Papers on Auction Algorithms, 1979-2001

 

My papers on auction algorithms for solving linear and convex network flow problems can be downloaded from here, including the original 1979 paper, an extensive tutorial paper, and an expository paper. The two network optimization books provide complementary accounts. Click here for codes.