Information Technology Reference
In-Depth Information
Ta b l e 1 .
Optimal settings of the parameters as a function of time
Time
Reward E
S
P
1.47
3318
64
1
1
Time Lower Upper E S P
0.03 468310 754507 10 1 1
0.04 517559 688963 10 2 1
0.07 535059 657833 10 3 1
0.11 548218 647722 10 4 1
0.29 550930 639010 10 5 1
0.38 554046 637546 100 5 1
0.40 559796 630666 10 6 1
0.56 561418 628053 100 6 1
1.31 562798 624235 100 7 1
1.36 567807 661136 100 3 8
1.58 575676 647877 100 4 7
2.84 577965 646174 100 4 13
3.06 579369 638006 100 5 9
4.13 581433 636296 100 5 13
5.47 582306 629457 100 6 9
5.65 582504 635982 100 5 17
7.30 583621 637376 100 5 21
8.50 583998 630956 100 6 13
9.44 584043 646170 100 4 43
10.00 584287 636188 100 5 29
10.92 585094 645841 100 4 49
12.63 585543 636626 100 5 37
1.48
3456
128 1
1
1.48
3502
2
1
1
1.49
3548
16
1
1
2.45
3550
32
4
1
2.45
3577
2
4
1
3.38
3695
2
1
2
3.89
3705
4
1
2
4.12
3912
128 8
1
4.16
3947
32
8
1
8.43
3967
2
16 1
10.55
4014
8
8
2
16.75
4043
32
8
2
17.95
4045
64
32 1
18.09
4064
1
32 1
18.12
4065
32
32 1
33.50
4077
32
8
4
38.52
4099
16
32 2
41.26
4132
32
64 1
82.20
4134
1
64 2
84.81
4136
32
32 4
85.99
4141
16
64 2
88.81
4142
32
64 2
115.27 4146
128 64 2
Bidding Problem
Scheduling Problem
techniques, we conducted an in-depth study of the SAA method itself, with one excep-
tion. We did measure the performance of the expected value method in the scheduling
problem, where all random variables are replaced with their means. Much like the re-
sults reported in [4], this method performs far worse than the SAA method, even with
only one scenario and one policy. The revenue earned was only 311,064 (as compared
to 468,310).
3
6Con lu ion
In this paper, we conducted an empirical study of the sample average approximation
method for solving stochastic optimization problems. We discovered that runtime can
increase exponentially with the number of scenarios, so that even if solution quality in-
creases exponentially with the number of scenarios, it may be advantageous to conduct
a policy search, because runtime increases only linearly with the number of policies. In
particular, we applied what we call the ESP methodology, which is a means of searching
3
The poor performance of the expected value method is partly due to the structure of the par-
ticular problem instances we solved. The expected value method should perform better on
problem instances with higher ratios of the number of orders to the number of computer types.
