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.
"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
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 (http://web.mit.edu/dimitrib/www/noc.htm).
"... 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-2020
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, "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 and D. A. Castanon, "The Auction
Algorithm for the Transportation Problem," Annals of Operations Research, Vol. 20, pp. 67-96,
D. P. Bertsekas, "An Auction Algorithm
for Shortest Paths," SIAM J. on Optimization,
Vol. 1, 1991, pp. 425-447.
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, "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
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, D. A. Castanon, and H. Tsaknakis, "Reverse Auction and the
Solution of Asymmetric Assignment Problems," SIAM J. on Optimization, Vol. 3, 1993,
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, 1993.
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,
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, 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,
"An Epsilon-Relaxation Method for Convex Network Optimization Problems,"
SIAM J. on Optimization, Vol. 7, 1997, pp. 853-870.
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, "Auction Algorithms," Encyclopedia of
Optimization, Kluwer, 2001. An 8-page expository article providing orientation,
references, and a summary overview of the subject.
Bertsekas, D., "Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm," arXiv preprint, arXiv:2002.07407 February 2020.
Papers on Multicommodity Flow Algorithms, 1982-2011
D. P. Bertsekas, "Centralized and Distributed Newton Methods for Network Optimization and Extensions," Lab. for Information and Decision
Systems Report LIDS-P-2866, MIT, April 2011.
A. E. Ozdaglar and D. P. Bertsekas,
"Routing and Wavelength Assignment in Optical Networks,"
Report LIDS-P-2535, Dec. 2001; IEEE Trans. on Networking, no. 2,
Apr. 2003, pp. 259-272.
A. E. Ozdaglar and D. P. Bertsekas,
"Optimal Solution of Integer Multicommodity Flow Problems with Application in
Optical Networks," Proc. of Symposium on Global Optimization, Santorini, Greece, June
2003; Frontiers in global optimization, pp. 411--435, Nonconvex Optim. Appl., 74, Kluwer Acad. Publ., Boston, MA, 2004.
J. N. Tsitsiklis, and D. P. Bertsekas, "Distributed Asynchronous Optimal Routing in Data Networks," IEEE
Trans. on Aut. Control, Vol. AC-31, 1986, pp. 325-332.
D. P. Bertsekas, E. Gafni, and R. G. Gallager, "Second Derivative Algorithms for Minimum Delay Distributed Routing in
Networks," IEEE Trans. on Communications, Vol. COM-32, 1984 p. 911.
D. P. Bertsekas and E. Gafni, "Projected Newton Methods and Optimization of Multicommodity Flows," IEEE
Trans. on Automatic Control, Vol. AC-28, 1983, pp. 1090-1096.
D. P. Bertsekas and E. Gafni, "Projection Methods for Variational
Inequalities with Applications to the Traffic Assignment Problem," Math.
Progr. Studies, Vol. 17, 1982, pp. 139-159.