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

Tuomas Sandholm (), Subhash Suri (), Andrew Gilpin () and David Levine ()
Additional contact information
Tuomas Sandholm: Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Subhash Suri: Department of Computer Science, University of California, Santa Barbara, California 93106
Andrew Gilpin: CombineNet, Inc., Fifteen 27th Street, Pittsburgh, Pennsylvania 15222
David Levine: CombineNet, Inc., Fifteen 27th Street, Pittsburgh, Pennsylvania 15222

Management Science, 2005, vol. 51, issue 3, 374-390

Abstract: Combinatorial auctions where bidders can bid on bundles of items can lead to more economically efficient allocations, but determining the winners is \scr{N}\scr{P}-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.

Keywords: 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 (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1040.0336 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:51:y:2005:i:3:p:374-390

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().