Auction algorithm

Auction algorithm

The term "auction algorithm" applies to several variations of a combinatorial optimization algorithm which solves assignment problems, and network optimization problems with linear and convex/nonlinear cost. An auction algorithm has been used in a business setting to determine the best prices on a set of products offered to multiple buyers. It is an iterative procedure, so the name "auction algorithm" is related to a sales auction, where multiple bids are compared to determine the best offer, with the final sales going to the highest bidders.

The original form of the auction algorithm is an iterative method to find the optimal prices and an assignment that maximizes the net benefit in a bipartite graph, the maximum weight matching problem (MWM). This algorithm was first proposed by Dimitri Bertsekas in 1979.

The ideas of the auction algorithm and ε-scaling

A later variation of the auction algorithm that solves shortest path problems was introduced by Bertsekas in 1991. It is a simple algorithm for finding shortest paths in a directed graph. In the single origin/single destination case, the auction algorithm maintains a single path starting at the origin, which is then extended or contracted by a single node at each iteration. Simultaneously, at most one dual variable will be adjusted at each iteration, in order to either improve or maintain the value of a dual function. In the case of multiple origins, the auction algorithm is well-suited for parallel computation.

Comparisons The (sequential) auction algorithms for the shortest path problem have been the subject of experiments which have been reported in technical papers.

Although with the auction algorithm the total benefit is monotonically increasing with each iteration, in the Hungarian algorithm (from Kuhn, 1955; Munkres, 1957) the total benefit strictly increases with each iteration.

The auction algorithm of Bertsekas for finding shortest paths within a directed graph is reputed to perform very well on random graphs and on problems with few destinations.

See also * Hungarian algorithm

References <references/>

External links * Dimitri P. Bertsekas. "Linear Network Optimization", MIT Press, 1991, [on-line](http://web.mit.edu/dimitrib/www/net.html). * Dimitri P. Bertsekas. "Network Optimization: Continuous and Discrete Models", [Athena Scientific, 1998](http://www.athenasc.com/netbook.html). Dimitri P. Bertsekas. "An auction algorithm for shortest paths", SIAM Journal on Optimization*, 1:425—447, 1991, webpage: [PSU-bertsekas91auction](http://citeseer.ist.psu.edu/bertsekas91auction.html). * D.P. Bertsekas, S. Pallottino, M. G. Scutella. "Polynomial Auction Algorithms for Shortest Paths," [Computational Optimization and Applications](https://doi.org/10.1007%2FBF01302891), Vol. 4, 1995, pp. 99-125. * Implementation of Bertsekas' Auction algorithm in Matlab by Florian Bernard, webpage: [Matlab File Exchange](http://de.mathworks.com/matlabcentral/fileexchange/48448-fast-linear-assignment-problem-using-auction-algorithm--mex-).