Starting Point

A core subproblem for TAC agents is the allocation problem: finding the most profitable allocation of goods to clients, $G^*$, given a set of owned goods and prices for all other goods. The allocation problem corresponds to finding $\mbox{opt}(H,i,Y)$ in Equation 3. We denote the value of $G^*$ (i.e., the score one would attain with $G^*$) as $v(G^*)$. 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 $v(G^*)$ is needed (as opposed to $G^*$ 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.