DESIGN
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
Lee, Li et al.
• Selection Rules – Zhao, Jia, Ho. • Optimal Allocation of Computing Budget – Chen, Lee et al • Constraint satisfaction – Song et al • Complete reference and applications list at end.
noise, w
130.741197 186.2304159 90.61091149 257.1674992 246.1330685 239.8111755 189.8911518
241.664179 374.4412696 204.4470437 340.2405253
356.149597 336.7832541 444.4689307 665.5127144 783.5096498 897.8429655 847.9866227 858.0134902 1023.014969 1082.184387 1056.412161 1229.769971 1075.175188 1182.823523 1183.446494 1300.723387 1393.320409 1273.545024 1403.761256 1408.789507 1563.524755 1538.953834
Orde r
39 22 122 6 20 77 168 155 26 198 69 56 115 14 2 112 62 169 173 49 21 102 24 188 178 196 98 59 184 110 187 71 129 37 132 29 140 43 12 96 54 121 124 136 199 164 163 158 73 175 116 50 152 30 9 84 118 52
Overview of Ordinal Optimization (OO)
By Yu-chi Ho
Harvard University & Tsinghua University
Acknowledgments
• Work of many people over a period of 13 years. • Supported by ONR, AFOSR, ARO, NSF, & EPRI. • First paper – 1992 (Ho, Screenivas, Vakili) • Convergence –Dai, Xie, Ho & Lau. • Multi-criteria and Constraints – Ho, Guan, Song, Zhao, Jia,
10/22/2020
Y.C. Ho
14
Selection Rules
• How do you select the estimated good enough set ,
S?
• Simplest rule is Blind Pick – se2020
Y.C. Ho
2
What Is OO?
• PROBLEM: Performance evaluation and
optimization of complex systems via simulation is extremely time consuming and often impossible.
• High cost and profit potential
10/22/2020
Y.C. Ho
6
Principles of OO
• “Order” vs. “Value” - The two box
metaphor
• Asking only for the “good enough” =>
Satisfying possibilities increases combinatorially
• Many decisions over time
• How much to disassemble • Out-source vs. Internal work • Parts inventory level • Repair vs. Replace • Preventive maintenance
Good Enough Threshold
10/22/2020
Y.C. Ho
9
A Live Demonstration
• 200 choices numbered from 1, . . . , 200 • Very large measurement noise U[0,100] or
U[0, 10000] added
10/22/2020
Y.C. Ho
12
In other words
OO theory tell you with high probability how many of the observed “good enough” set obtained using very crude models are indeed truly “good enough” - the Alignment Probability (AP)
Xie)
10/22/2020
A
B
Y.C. Ho
Performance
8
Major OO Result II
• Satisfactory results increases
combinatorially with the size of Good Enough threshold (Ho Lau and Lee 1999)
reset
Expt #1
Expt #2
Expt #3
add noise
order
Alignment
Average G intersect S 0
Infinite noise
Blindpick
10/22/2020
Y.C. Ho
11
OO How-to
• Create a crude model of the performance • Evaluate N samples of the crude model • Define s=|S| members of N as the selected
How many of the top 16 seeds in tennis will reach the quarter final in U.S. Open?
10/22/2020
Y.C. Ho
13
What about the “Ranking &
Selection” Literature?
• R&S problems deals with a few alternatives • OO search space Q are of size in billions
• Select top-12 (top 6%) using noisy
measurements
• Check alignment between S and G, the true
top-12.
• Open OO demo.xls and play!
10/22/2020
Y.C. Ho
10
Illustration of OO demo.xls. Go to EXCEL to open and play
TRUE PERFORMANCE
J 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
1832.44107 1750.669524 1878.818435 1832.400723
2012.25718 2062.64469 2015.538174 2069.805204 2003.031773 2000.904922 2162.323516 2202.229017 2267.614046 2350.820323 2379.884515 2521.66779 2467.525538 2577.967978 2653.386595 2630.714805 2770.569753 2841.383177 2769.988868 2872.570794 2940.177555
• SOLUTION: OO renders the above difficult
problem feasible.
• OO is very general and can be applied
anywhere.
10/22/2020
Y.C. Ho
3
A Typical Real World Problem (contd.)
and billions
• R&S are interested in “distance of best from
the rest” – a cardinal notion
• R&S are interested in the Probability that