  Previous works suggested the use of Branch and Bound techniques for finding
the optimal allocation in (multi-unit) combinatorial auctions. They remarked
that Linear Programming could provide a good upper-bound to the optimal
allocation, but they went on using lighter and less tight upper-bound
heuristics, on the ground that LP was too time-consuming to be used
repetitively to solve large combinatorial auctions. We present the results of
extensive experiments solving large (multi-unit) combinatorial auctions
generated according to distributions proposed by different researchers. Our
surprising conclusion is that Linear Programming is worth using. Investing
almost all of one's computing time in using LP to bound from above the value of
the optimal solution in order to prune aggressively pays off. We present a way
to save on the number of calls to the LP routine and experimental results
comparing different heuristics for choosing the bid to be considered next.
Those results show that the ordering based on the square root of the size of
the bids that was shown to be theoretically optimal in a previous paper by the
authors performs surprisingly better than others in practice. Choosing to deal
first with the bid with largest coefficient (typically 1) in the optimal
solution of the relaxed LP problem, is also a good choice. The gap between the
lower bound provided by greedy heuristics and the upper bound provided by LP is
typically small and pruning is therefore extensive. For most distributions,
auctions of a few hundred goods among a few thousand bids can be solved in
practice. All experiments were run on a PC under Matlab.
