CABRO: Winner Determination Algorithm for Single-unit Combinatorial Auctions
作者： Víctor Muòoz , Javier Murillo
DOI:
关键词:
摘要: In this paper we present CABRO, an algorithm for solving the winner determination problem related to single-unit combinatorial auctions. The is divided in three main phases. first phase a pre-processing step with some reduction techniques. second calculates upper and lower bound based on linear programming relaxation order delete more bids. Finally, third branch depth search where used as bounding sorting strategy. Experiments against specific solvers like CASS general purpose MIP GLPK CPLEX show that CABRO average fastest free solver (CPLEX not included), instances drastically faster than any other.
参考文章(10)
Tuomas Sandholm, Andrew Gilpin, Subhash Suri, David Levine, CABOB: a fast optimal algorithm for combinatorial auctions international joint conference on artificial intelligence. pp. 1102- 1108 ,(2001)
日本科学技術連盟, George Bernard Dantzig, THE SIMPLEX METHOD Union of Japanese Scientists & Engineers. ,(1956)
Dale Schuurmans, Finnegan Southey, Robert C. Holte, The exponentiated subgradient algorithm for heuristic Boolean programming international joint conference on artificial intelligence. pp. 334- 341 ,(2001)
Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions Artificial Intelligence. ,vol. 135, pp. 1- 54 ,(2002) , 10.1016/S0004-3702(01)00159-X
Kevin Leyton-Brown, Mark Pearson, Yoav Shoham, Towards a universal test suite for combinatorial auction algorithms electronic commerce. pp. 66- 76 ,(2000) , 10.1145/352871.352879
Sven De Vries, Rakesh V Vohra, Northwestern University (Evanston, Ill.). Center for Mathematical Studies in Economics and Management Science, Combinatorial Auctions: A Survey Informs Journal on Computing. ,vol. 15, pp. 284- 309 ,(2003) , 10.1287/IJOC.15.3.284.16077
Holger H. Hoos, Craig Boutilier, Solving Combinatorial Auctions Using Stochastic Local Search national conference on artificial intelligence. pp. 22- 29 ,(2000)
Kevin Leyton-Brown, Yoav Shoham, Yuzo Fujishima, Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches international joint conference on artificial intelligence. pp. 548- 553 ,(1999)
Michael H. Rothkopf, Aleksandar Pekeč, Ronald M. Harstad, Computationally Manageable Combinational Auctions Management Science. ,vol. 44, pp. 1131- 1147 ,(1998) , 10.1287/MNSC.44.8.1131
Peter Cramton, Yoav Shoham, Richard Steinberg, Combinatorial Auctions ,(2005)