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://faculty.engineering.asu.edu/bertsekas/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 Preface, Chapter 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.

• D. P. Bertsekas, “A Distributed Algorithm for the Assignment Problem,” Lab. for Information and Decision Systems Report, MIT, May 1979. The original paper, which includes the auction algorithm with epsilon scaling.
• D. P. Bertsekas, “A New Algorithm for the Assignment Problem,” Mathematical Programming, Vol. 21, pp. 152-171, 1981. Contains the naive version of the auction algorithm (which does not use epsilon), and its combination with the Hungarian method (this is the basis for the widely used JV code for linear assignment problems).
• D. P. Bertsekas, “Distributed Relaxation Methods for Linear Network Flow Problems,” Proc. of 25th CDC, Athens, Greece, 1986, pp. 2101-2106. The original epsilon-relaxation/preflow push paper.
• D. P. Bertsekas, “Auction Algorithms for Network Flow Problems: A Tutorial Introduction,” Computational Optimization and Applications, Vol. 1, pp. 7-66, 1992. An extensive tutorial paper that surveys auction algorithms, a comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems.
• D. P. Bertsekas, “Auction Algorithms,” Encyclopedia of Optimization, Kluwer, 2001. An 8-page expository article providing orientation, references, and a summary overview of the subject.
  

  ---

• D. P. Bertsekas, “The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem,” Annals of Operations Research, Vol. 14, 1988, pp. 105-123.
• D. P. Bertsekas and J. Eckstein, “Dual Coordinate Step Methods for Linear Network Flow Problems,” Mathematical Programming, Series B, Vol. 42, 1988, pp. 203-243.
• D. P. Bertsekas, Mathematical Equivalence of the Auction Algorithm for Assignment and the Epsilon-Relaxation (Preflow-Push) Method for Min Cost Flow,” In: Large Scale Optimization, Hager W.W., Hearn D.W., Pardalos P.M. (eds), Springer, Boston, MA.
• D. P. Bertsekas and D. A. Castanon, “The Auction Algorithm for the Transportation Problem,” Annals of Operations Research, Vol. 20, pp. 67-96, 1989.
• D. P. Bertsekas, D. A. Castanon, and H. Tsaknakis, “Reverse Auction and the Solution of Asymmetric Assignment Problems,” SIAM J. on Optimization, Vol. 3, 1993, pp. 268-299.
• D. P. Bertsekas and D. A. Castanon, “A Forward Reverse Auction Algorithm for Asymmetric Assignment Problems,” Report LIDS-P-2159, Lab. for Information and Decision Systems, also Computational Optimization and Applications, Vol. 1, pp. 277-297, 1992.
• D. P. Bertsekas and D. A. Castanon, “Parallel Synchronous and Asynchronous Implementations of the Auction Algorithm,” Parallel Computing, Vol. 17, pp. 707-732, 1991.
• D. P. Bertsekas, and D. A. Castanon, “A Generic Auction Algorithm for the Minimum Cost Network Flow Problem,” Computational Optimization and Applications, Vol. 2, 1993, pp. 229-260.
• D. P. Bertsekas, “An Auction/Sequential Shortest Path Algorithm for the Minimum Cost Flow Problem,” Report LIDS-P-2146, Lab. for Info. and Decision Systems, Revision of Feb. 1995.
• D. P. Bertsekas, “An Auction Algorithm for Shortest Paths,” SIAM J. on Optimization, Vol. 1, 1991, pp. 425-447.
• D. P. Bertsekas, S. Pallottino, and M. G. Scutella, “Polynomial Auction Algorithms for Shortest Paths,” Computational Optimization and Applications , Vol. 4, 1995, pp. 99-125.
• D. P. Bertsekas, “An Auction Algorithm for the Max-Flow Problem,” J. of Optimization Theory and Applications, Vol. 87, 1995, pp. 69-101.
• D. P. Bertsekas, L. C. Polymenakos, and P. Tseng, “Epsilon-Relaxation and Auction Methods for Separable Convex Cost Network Flow Problems,” in Network Optimization, by P. M. Pardalos, D. W. Hearn, and W. W. Hager (eds.), Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, N.Y., 1998, pp. 103-126.
• D. P. Bertsekas, L. C. Polymenakos, and P. Tseng, “An Epsilon-Relaxation Method for Convex Network Optimization Problems,” SIAM J. on Optimization, Vol. 7, 1997, pp. 853-870.