Information Technology Reference
In-Depth Information
4
Experiments
The goal of our experiments was to optimize the parameters
E
,
S
,and
P
in Algorithm 1
in our two sample problems, given time (and space) constraints. At a high level, we ran
multiple trials (that is, we solved multiple instances of each problem), with multiple
settings of the parameters, and we averaged our results across trials to find the best pa-
rameter settings within reasonable time and space constraints. More specifically, our
tests were conducted as follows: for each setting of the parameters (
E, S, P
),andfor
each trial
t
=1
,...,T
, we (i) generated a problem instance; (ii) ran Algorithm 1 to
find the best policy; (iii) evaluated that policy using
E
>E
scenarios.
2
For the bidding
problem we set
T
=50and
E
= 250,andwelet
E
∈{
1
,
2
,
4
,
8
,
16
,
32
,
64
,
128
}
and
. For the scheduling problem, we set
T
= 100 and
E
=
S, P
∈{
1
,
2
,
4
,
8
,
16
,
32
,
64
}
5000,andwelet
E
.
All experiments were run on an AMD Athlon 64 3000+ with 1GB of RAM. We used
CPLEX 9.0 to solve the integer programs, solving to within .01% of optimality with the
default settings.
∈{
10
,
100
,
500
,
1000
}
,
S
∈{
1
,...,
8
}
,and
P
∈{
1
,...,
375
}
4.1
Hypotheses
Our first set of experiments was intended to approximate the time complexity of the
bidding problem and the scheduling problem. The graphs in Figure 1 depict time (in
seconds) as a function of
S
, for fixed values of
E
and
P
. Perhaps surprisingly, in the
bidding problem, this relationship is approximately linear. In the scheduling problem,
however, time increases rapidly as the number of scenarios increases. The error bars in
these graphs plot one standard deviation from the mean. The variance in these experi-
ments is large, because we average results across multiple trials: i.e., problem instances
of varying degrees of difficulty.
Figure 2 depicts the agent's reward in the bidding problem and its revenue in the
scheduling problem, as a function of
S
and
P
. Here, we observe that increasing the
number of scenarios from 1 to 64 in the bidding problem leads to an increase in reward
from roughly 3300 to roughly 4200, on average. In the scheduling problem, increasing
the number of policies, say from 1 to 20, leads to a substantial increase in revenue, but at
32 policies, revenue seems to stabilize. Of course, increasing the number of scenarios
also leads to an increase in revenue, but in practice this may not be feasible. Indeed,
revenue is still increasing between 7 and 8 scenarios, but we cannot solve this problem
reliably with as few as 9 scenarios.
Based on these observations, we postulate the following: In problems, like the bid-
ding problem, where time complexity is an approximately linear function of
S
, a near
optimal setting of the parameters can be obtained by setting
S
to the maximum value
possible within the time and space constraints of the application, and then perhaps in-
creasing
P
if time and space permit. On the other hand, in problems like the scheduling
problem, where time complexity is a superlinear function of
S
, it is necessary to search
the space of parameter settings, within the time and space constraints of the applica-
2
Anecdotally, we report that more evaluations were necessary to accurately estimate the value
of a policy, but fewer evaluations were sufficient to rank policies.
