  Finding optimal solutions for multi-unit combinatorial auctions is a hard
problem and finding approximations to the optimal solution is also hard. We
investigate the use of Branch-and-Bound techniques: they require both a way to
bound from above the value of the best allocation and a good criterion to
decide which bids are to be tried first. Different methods for efficiently
bounding from above the value of the best allocation are considered.
Theoretical original results characterize the best approximation ratio and the
ordering criterion that provides it. We suggest to use this criterion.

Computer Science and Game Theory;Artificial Intelligence