NETWORK OPTIMIZATION - AUCTION ALGORITHMS

Dimitri P. Bertsekas

Books, research papers, surveys, and other resources (1979 to the present)



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

netcover.jpg

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.

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

Linear_Net_Optimization_Cover.jpg

This 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 originally given in this book can be downloaded from here.


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



Network Optimization Codes

Several network optimization codes by the author, many of them based on auction and relation methods can be found in this site. The Athena Scientific site contains references to related software by others.



Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning

A new book in preparation; Athena Scientific

The purpose of this monograph is to present new research and an up-to-date account relating to the auction algorithm for the classical assignment problem, introduced by the author in his 1979 paper "A Distributed Algorithm for the Assignment Problem," Lab. for Information and Decision Systems Report, MIT, and studied together with its variations over a period of more than 40 years, including a detailed treatment in the book "Network Optimization: Continuous and Discrete Models," Athena Scientific, 1998 (free PDF given above).

The auction algorithm is highly intuitive, and involves a market-based mechanism that resembles a real-life auction. Other features of the algorithm are that it has excellent computational complexity, and it is amenable to distributed asynchronous implementation. We describe the auction algorithm and its properties for the assignment problem, and we will focus on adaptations of the algorithm to solve other network optimization problems, including new methods for path planning and network transport problems.

Much of the new research in this book relates to adaptations of the auction algorithm for the assignment problem, which apply to path construction problems, including the classical shortest path problem. Auction algorithms for path construction have an intuitive form, and will be used as the basis for solution of other problems, including max-flow, transportation, and transhipment problems. Auction/path construction algorithms will also be applied, in both exact and approximate form, in an important application area: reinforcement learning and sequential decision making, particularly in contexts where the popular Monte Carlo tree search and real-time dynamic programming methods have been used.

The monograph represents ``work in progress," and will be periodically updated. It more than likely contains errors (hopefully not serious ones). Furthermore, the references to the literature are incomplete. Your comments and suggestions to the author at dimitrib@mit.edu or dbertsek@asu.edu are welcome.

Book Chapters:


Preface - Table of Contents

Chapter 1: Auction Algorithms - An Introduction

Chapter 2: Auction Algorithms for the Assignment Problem

Chapter 3: Auction Algorithms for Path Planning

Chapter 4: Auction Algorithms for Network Transport

Chapter 5: Auction Algorithms for Reinforcement Learning

References


Related research papers:

Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning, ASU Research Report; an early version of the paper was posted at arXiv:22207.09588 in July 2022.

New Auction Algorithms for the Assignment Problem and Extensions, ASU Research Report; an early version of the paper was posted at arXiv:2310.03159 in Oct. 2023.



Papers on Auction Algorithms, 1979-2022

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. A typeset version of the typewritten original.

  • 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, 1989.

  • 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 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, pp. 268-299.

  • 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, 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, 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.

  • D. P. Bertsekas, "Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm," arXiv preprint, arXiv:2002.07407 February 2020.

  • D. P. Bertsekas, "Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning," Arizona State University/SCAI Report, July 2022.

  • Bertsekas, D., "New Auction Algorithms for the Assignment Problem and Extensions," ASU Research Report, Oct. 2023; arXiv:2310.03159.


    Tutorial Papers on Auction Algorithms

  • 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 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, "The Auction Algorithm for Assignment and Other Network Flow Problems: A Tutorial," Interfaces, Vol. 20, pp. 133-149. A lighter/shorter tutorial paper that focuses on the assignment problem.


    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.


    Accessibility