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

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.

"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

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.

"... 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.