CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions
提出CABOB算法，通过分解、上下界和启发式排序等方法，快速求解组合拍卖中的胜者确定问题，实验表明其速度常优于CPLEX，尤其适合有结构的问题。
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.