This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Sandholm, T. Articles by Levine, D. Search for Related Content

CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions

Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Department of Computer Science, University of California, Santa Barbara, California 93106
CombineNet, Inc., Fifteen 27th Street, Pittsburgh, Pennsylvania 15222
CombineNet, Inc., Fifteen 27th Street, Pittsburgh, Pennsylvania 15222
sandholm{at}cs.cmu.edu
suri{at}cs.ucsb.edu
agilpin{at}combinenet.com
dlevine{at}combinenet.com

Combinatorial auctions where bidders can bid on bundles of items can lead to more economically efficient allocations, but determining the winners is -complete and inapproximable. We present CABOB, a sophisticated optimal search algorithm for the problem. It uses decomposition techniques, upper and lower bounding (also across components), elaborate and dynamically chosen bid-ordering heuristics, and a host of structural observations. CABOB attempts to capture structure in any instance without making assumptions about the instance distribution. Experiments against the fastest prior algorithm, CPLEX 8.0, show that CABOB is often faster, seldom drastically slower, and in many cases drastically faster—especially in cases with structure. CABOB's search runs in linear space and has significantly better anytime performance than CPLEX.

We also uncover interesting aspects of the problem itself. First, problems with short bids, which were hard for the first generation of specialized algorithms, are easy. Second, almost all of the CATS distributions are easy, and the run time is virtually unaffected by the number of goods. Third, we test several random restart strategies, showing that they do not help on this problem—the run-time distribution does not have a heavy tail.

Key Words: auction; combinatorial auction; winner determination; winner-determination algorithm; search; branch and bound; MIP; anytime algorithm; branching heuristics; dynamically chosen heuristic; bounding across components; random restart
History: Received: June 4, 2002;

This article has been cited by other articles:

				R. L.-Y. Chen, S. AhmadBeygi, A. Cohn, D. R. Beil, and A. Sinha Solving Truckload Procurement Auctions Over an Exponential Number of Bundles Transportation Science, November 1, 2009; 43(4): 493 - 510. [Abstract] [PDF]

				R. W. Day and S. Raghavan Matrix Bidding in Combinatorial Auctions Operations Research, July 1, 2009; 57(4): 916 - 933. [Abstract] [PDF]

				T. Sandholm, D. Levine, M. Concordia, P. Martyn, R. Hughes, J. Jacobs, and D. Begg Changing the Game in Strategic Sourcing at Procter & Gamble: Expressive Competition Enabled by Optimization Interfaces, January 1, 2006; 36(1): 55 - 68. [Abstract] [PDF]

				G. Anandalingam, R. W. Day, and S. Raghavan The Landscape of Electronic Market Design Management Science, March 1, 2005; 51(3): 316 - 327. [Abstract] [PDF]