Auction algorithm
Encyclopedia
The term "auction algorithm" applies to several variations of a combinatorial optimization
algorithm
which solves assignment problem
s, 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. Detailed analysis and extensions to more general network optimization problems (epsilon-relaxation and network auction algorithms) are provided in his network optimization books Linear Network Optimization 1991, and Network Optimization: Continuous and Discrete Models 1998. The auction algorithm has excellent computational complexity, as given in these books, and is reputed to be among the fastest for solving single commodity network optimization problems.
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. The algorithm is closely related to auction algorithms for other network flow problems. According to computational experiments, the auction algorithm is generally inferior to other state-of-the-art algorithms for the all destinations shortest path problem, but is very fast for problems with few destinations (substantially more than one and substantially less than the total number of nodes); see the article by Bertsekas, Pallottino, and Scutella, Polynomial Auction Algorithms for Shortest Paths.
Auction algorithms for shortest hyperpath problems have been defined by De Leone and Pretolani in 1998. This is also a parallel auction algorithm for weighted bipartite
matching, described by E. Jason Riedy in 2004.
Although in the auction algorithm, each iteration never decreases the total benefit (increases or remains the same), with the alternative Hungarian algorithm
(from Kuhn, 1955; Munkres, 1957), each iteration always increases the total.
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.
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
which solves assignment problem
Assignment problem
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics...
s, 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
Auction
An auction is a process of buying and selling goods or services by offering them up for bid, taking bids, and then selling the item to the highest bidder...
, 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
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
, the maximum weight matching problem (MWM).
This algorithm was first proposed by Dimitri Bertsekas
Dimitri Bertsekas
Dimitri Bertsekas is an applied mathematician and computer scientist, and a professor at the department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology , Cambridge, Massachusetts.- Biography :...
in 1979. Detailed analysis and extensions to more general network optimization problems (epsilon-relaxation and network auction algorithms) are provided in his network optimization books Linear Network Optimization 1991, and Network Optimization: Continuous and Discrete Models 1998. The auction algorithm has excellent computational complexity, as given in these books, and is reputed to be among the fastest for solving single commodity network optimization problems.
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
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
. 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. The algorithm is closely related to auction algorithms for other network flow problems. According to computational experiments, the auction algorithm is generally inferior to other state-of-the-art algorithms for the all destinations shortest path problem, but is very fast for problems with few destinations (substantially more than one and substantially less than the total number of nodes); see the article by Bertsekas, Pallottino, and Scutella, Polynomial Auction Algorithms for Shortest Paths.
Auction algorithms for shortest hyperpath problems have been defined by De Leone and Pretolani in 1998. This is also a parallel auction algorithm for weighted bipartite
Bipartite
Bipartite means having two parts, or an agreement between two parties. More specifically, it may refer to any of the following:-Mathematics:* 2 * bipartite graph* bipartite cubic, a type of cubic function-Medicine:...
matching, described by E. Jason Riedy in 2004.
Comparisons
The (sequential) auction algorithms for the shortest path problem have been the subject of experiments which have been reported in technical papers. Experiments clearly show that the auction algorithm is inferior to the state-of-the-art shortest-path algorithms for finding the optimal solution.Although in the auction algorithm, each iteration never decreases the total benefit (increases or remains the same), with the alternative Hungarian algorithm
Hungarian algorithm
The Hungarian method is a combinatorial optimization algorithm which solves the assignment problem in polynomial time and which anticipated later primal-dual methods...
(from Kuhn, 1955; Munkres, 1957), each iteration always increases the total.
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.
External links
- Dimitri P. Bertsekas. "An auction algorithm for shortest paths", SIAM Journal on Optimization, 1:425—447, 1991, webpage: PSU-bertsekas91auction.
- Bertsekas, S. Pallottino, and M. G. Scutella, "Polynomial Auction Algorithms for Shortest Paths," , Computational Optimization and Applications, Vol. 4, 1995, pp. 99-125.