# Geeking out on tree searches

In the course of thinking about the semi-Seekrit Project (which I totally do not have time for, not even if I bust out of my poker tournament early tomorrow) I picked up the Combinatorial Auctions book again (edited by Cramton, Shoham, and Steinberg) to discover that I had left off just at a very relevant point--- the computational complexity and feasibility of winner determination.

Chapter 14 by Tuomas Sandholm on "Optimal Winner Determination Algorithms" is realy a tour-de-force on search optimization. The problems in question are (except for very limited cases) provably NP-hard (the subject of chapters 12 and 13), so what sort of results can be achieved in practice?

Even the most basic question, what to use as the search space, is an interesting one: obviously you could search over all items in the combinatorial auctions, or over all bids. But there is a third category as well: you can branch on the sum of a set of variables in the problem. For example, one branch of the search could be "at least three of these eleven bids are winners" while the other branch is its negation. Sandholm next covers search "strategies" (depth-first, depth-first branch-and-bound, A*, iterative deepening.)

But we really get moving with an example algorithm, CABOB. The ideas introduced in this context are an impressive list:

• upper bounds and using LP solutions (to a relaxation of the integer problem) as upper bounds
• cutting planes and lower bounds
• decomposition of the problem, applying upper and lower bounds across the components after doing so
• selecting the next branch decision heuristically:

• to favor greater decomposition, or
• based on the certainty or uncertainty of the answer (the answer is different for different search strategies!), or
• based on the result of a 'seed' search that produced an approximate answer, or
• based on the duals from the LP used for bounding! Or other application-specific metrics.

• identifying subproblems which are tractable special cases
• random restart
• caching (memoization) of subproblems

Although he's talking about a specific problem, this is a pretty good catalog of the techniques that are available for going beyond a bare search algorithm to one that "intelligently" explores the space.

Sandholm mentions a couple times that the difference between good and bad techniques can be two orders of magnitude. He says that "On easier distributions.... optimal winner determination scales to hundreds or thousands of items, and tens of thousands of bids in seconds. On hard distributions... optimal winner determination only scales to tens of items and hundreds of bids in a minute."

It looks like he has an online version of this chapter available.
Tags:
• Post a new comment

#### Error

default userpic