Information Technology Reference
In-Depth Information
Algorithm 1.
Sample Average Approximation (
E, S, P
)
1: bestval
⇐−∞
2: sampleaset
E
of
E
scenarios according to
Q
3:
for all
j
=1to
P
do
4:
sampleaset
S
of
S
scenarios according to
Q
5:
x ⇐
arg max
x∈X
g
S
(
x
)
6:
calculate
g
E
(
x
)
7:
if
g
E
(
x
)
>
bestval
then
8:
bestval
⇐ g
E
(
x
)
⇐ x
9:
bestsol
10:
end if
11:
end for
12: return bestsol
space complexity required to solve Equation 4 may increase superlinearly, making it
impossible—for all practical purposes—to allow
S
to suitably increase, unless the de-
sired optimality gap is sufficiently
large
. Rather than fix the number of policies
P
,and
vary only
S
and
E
, we apply the SAA method by searching for optimal settings of
E
,
S
,and
P
, given the time and space constraints of the problem.
2.1
Overview
In solving stochastic optimization problems, not only can increasing the number of sce-
narios
S
increase the quality of the solution, but increasing the number of policies
P
can also increase the quality of the solution (the probability that the (
P
+1)st policy
outperforms the first
P
policies is 1
/
(
P
+1)). Moreover, in Algorithm 1, the time com-
plexity is linear in
P
and the space complexity is constant in
P
, but increasing
S
could
increase time and space complexity in unpredictable ways because of the intricacies of
Equation 4. In this paper, we study two stochastic optimization problems in the TAC
domain, analyzing the tradeoff between solution quality and complexity, with respect
to
E
,
S
,and
P
.
3
Sample Problem Domains
In this paper, we study two sample problem domains—stochastic bidding and stochastic
scheduling—both
inspired
by
the
annual
Trading
Agent
Competition
(see
http://www.sics.se/tac
, [11], [2]).
3.1
Stochastic Bidding Problem
We solve a stochastic bidding problem inspired by the classic Trading Agent Compe-
tition game. In this game, each agent's objective is to maximize the profits earned by
delivering combinations of 28 types of goods, on offer in 28 auctions, to eight clients.
The stochastic formulation of the bidding problem can be described informally as fol-
lows: given a stochastic model of auction clearing prices, and given an agent's clients'
