** Next:** Overview
** Up:** ATTac-2001
** Previous:** ATTac-2001

##

Starting Point

A core subproblem for TAC agents is the allocation problem: finding
the most profitable allocation of goods to clients, , given a
set of owned goods and prices for all other goods. The allocation
problem corresponds to finding
in
Equation 3. We denote the value of (*i.e.*, the
score one would attain with ) as . The general
allocation problem is NP-complete, as it is equivalent to the
set-packing problem [Garey JohnsonGarey Johnson1979]. However it can be solved
tractably in TAC via integer linear programming [Stone, Littman, Singh, KearnsStone
et al.2001].

The solution to the integer linear program is a value-maximizing
allocation of owned resources to clients along with a list of
resources that need to be purchased. Using the linear programming
package ``LPsolve'', *ATTac-2001* is usually able to find the globally
optimal solution in under 0.01 seconds on a 650 MHz Pentium
II. However, since integer linear programming is an NP-complete
problem, some inputs can lead to a great deal of search over the
integrality constraints, and therefore significantly longer solution
times. When only is needed (as opposed to itself), the upper bound produced by LPsolve prior to the search over
the integrality constraints, known as the LP relaxation, can be used
as an estimate. The LP relaxation can always be generated very
quickly.

Note that this is not by any means the only possible formulation of
the allocation problem. boyan01 boyan01 studied a fast, heuristic
search variant
and found that it performed extremely well on a collection of large,
random allocation problems. JAIR-tac00 JAIR-tac00 used a randomized
greedy strategy as a fallback for the cases in which the linear
program took too long to solve.

** Next:** Overview
** Up:** ATTac-2001
** Previous:** ATTac-2001
Peter Stone
2003-09-24