Optimal computing budget allocation

Optimal computing budget allocation (OCBA) is a concept first introduced in the mid 1990s by Dr. Chun-Hung Chen. This approach intends to maximize the overall simulation efficiency for finding an optimal decision.^[1] Simply put, OCBA is an approach to simulation that will help determine the number of replication and/or the simulation time that is needed in order to receive acceptable/best results within a set of given parameters.^[2] This is accomplished by using an asymptotic framework to analyze the structure of the optimal allocation.^[3]

Intuitive explanations

OCBA’s goal is to provide a systematic approach to run a large number of simulations including only the critical alternatives in order to select the best alternative. In other words, focusing on only part the most critical alternatives, which minimizes computation time and reduces these critical estimators’ variances. The expected result maintains the required level of accuracy, while requiring less amount of work.^[4] For example we can create a simple simulation between 5 alternatives. The goal is to select an alternative with minimum average delay time. The figure below shows preliminary simulation results ( i.e. having run only a fraction of the required number of simulation replications). It is clear to see that alternative 2 and 3 have a significantly lower delay time ( highlighted in red). In order to save computation cost (which is time, resources and money spend on the process of running the simulation) OCBA suggests that more replications are required for alternative 2 and 3, and simulation can be stopped for 1, 4, and 5 much earlier without compromising results.

What problem does OCBA intend to solve

The main objective of OCBA is to maximize the probability of correct selection (PCS). PCS is subject to the sampling budget of a given stage of sampling τ.

${\displaystyle {\begin{aligned}&\max _{\tau _{1},\tau _{2},\ldots ,\tau _{k}}\mathrm {PCS} \\&{\text{subject to }}\sum _{i=1}^{k}\tau _{i}\geq 0.\qquad (1)\end{aligned}}}$

In this case ${\displaystyle \sum _{i=1}^{k}\tau _{i}=\tau }$ stands for the total computational cost.^[5]

Main OCBA results

The main results of OCBA is done by taking into consideration an asymptotic case. In this case (τ) begins to increase toward ∞ in such a way that the total sampling budget β increases to ∞ and τ_i also increases to n_i). Using Equation 1 from section "What problem does OCBA intend to solve" PCS can be maximized by the following 2 Equations.

(insert equations 1 and 2 here – the article needs to be published first in order to add copyrighted images – I have permission by the author to publish the specific images .

Something interesting to notice is that Equation 2 suggests that the number of replications for each alternative i is proportional to the square noise-to-signal ratio. To clarify noise is referring to the sample Standard deviation and signal is referring to the difference between i's sample mean and the best sample mean.

One numerical testing example

OCBA was put to the test when numerical results were published using a simple example that is shown in figure 1. The goal is to allocate 31 parallel servers within a two-stage queuing system. A constraint in this example is that each queue (p1, p2) can have no less than 11 servers. Mathematically put: p₁ + p₂ = 31, p₁ > 11 and p₂ > 11.

Given this information we can see that there are 10 alternative computations (p₁, p₂). The goal is to minimize the customer wait time for the first 100 customers. In order to express the performance of different procedures, we introduce a function β computational budget (i.e. resources used such as time, power) which we will vary between 200 and 8000 for all of the sequential procedures. The estimated PCS is a function of β. PCS is estimated by the fraction of the event of correct selection out of the independent experiment that were conducted. The results of varying β and its corresponding PCS are shown in Figure 2. FIGURE 2 goes here – the article needs to be published first in order to add copyrighted images – I have permission by the author to publish the specific images

Table 2 shows the numerical results of Figure 2. The sampling budget to attain a PCS of 0.95 and 0.99 is compared using OCBA allocation and equal allocation.

PCS	OCBA	Equal allocation
0.95	470	1450
0.99	850	2890

Next, we are doing a separate experiment with multiple alternatives that are called k. For example we can now have more than 31 servers. We can observe the speedup factor of reaching a desired level of PCS. In this case it is .99. Table 3 shows the speedup factor using OCBA compared with the equal allocation method. The Speedup factor is calculated by β_EA/ β_OCBA. We can see that as the number of alternatives increases so does the speedup factor. This is how computation time is saved when performing simulations with large number of alternatives.

Number of alternatives (k)	4	10	20	50	75	100
Speedup factor	1.75	3.42	6.45	12.8	16.3	19.8

^[6]

Some extensions of OCBA

Experts in the field explain that in some problems it is important to not only know the best alternative among a sample, but the top 5, 10, or even 50, because the decision maker may have other concerns that may affect the decision which are not modeled in the simulation. According to Szechtman and Yücesan (2008),^[7] OCBA is also helpful in feasibility determination problems. This is where the decisions makers are only interested in differentiating feasible alternatives from the infeasible ones. Further, choosing an alternative that is simpler, yet similar in performance is crucial for other decision makers. In this case, the best choice is among top-r simplest alternatives, whose performance rank above desired levels.^[8] In addition, Trailovic^[9] and Pao^[10] (2004) demonstrate an OCBA approach, where we find alternatives with minimum variance, instead of with best mean. Here, we assume unknown variances, voiding the OCBA rule (assuming that the variances are known). During 2010 research was done on an OCBA algorithm that is based on a t distribution. The results show no significant differences between those from t-distribution and normal distribution. The above presented extensions of OCBA is not a complete list and is yet to be fully explored and compiled.^[6]

Multi-objective Optimal Computing Budget Allocation

Multi-objective Optimal Computing Budget Allocation (MOCBA) is the OCBA concept that applies to multi-objective problems. In a typical MOCBA, the PCS is defined as

${\displaystyle \Pr\{CS\}\equiv \Pr \left\{\left(\bigcap _{i\in S_{p}}E_{i}\right)\bigcap \left(\bigcap _{i\in {\overline {S}}_{p}}E_{i}^{c}\right)\right\},}$

in which

• $S_{p}$ is the observed Pareto set,
• ${\displaystyle {\overline {S}}_{p}}$ is the non-Pareto set, i.e., ${\displaystyle {\overline {S}}_{p}=\Theta \backslash S_{p}}$,
• $E_{i}$ is the event that design $i$ is non-dominated by all other designs,
• ${\displaystyle E_{i}^{c}}$ is the event that design $i$ is dominated by at least one design.

We notice that, the Type I error $e_{1}$ and Type II error $e_{2}$ for identifying a correct Pareto set are respectively

${\displaystyle e_{1}=1-\Pr \left\{\bigcap _{i\in {\overline {S}}_{p}}E_{i}^{c}\right\}}$ and ${\displaystyle e_{2}=1-\Pr \left\{\bigcap _{i\in S_{p}}E_{i}\right\}}$.

Besides, it can be proven that

${\displaystyle e_{1}\leq ub_{1}=H\left|{\overline {S}}_{p}\right|-H\sum _{i\in {\overline {S}}_{p}}{\max _{j\in \Theta ,j\neq i}\left[\min _{l\in {1,\ldots ,H}}\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\}\right]}}$

and

${\displaystyle e_{2}\leq ub_{2}=(k-1)\sum _{i\in S_{p}}\max _{j\in \Theta ,j\neq i}\left[\min _{l\in {1,\ldots ,H}}\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\}\right],}$

where $H$ is the number of objectives, and ${\displaystyle {\tilde {J}}_{il}}$ follows posterior distribution ${\displaystyle Normal\left({\bar {J}}_{il},{\frac {\sigma _{il}^{2}}{N_{i}}}\right).}$ Noted that ${\displaystyle {\bar {J}}_{il}}$ and ${\displaystyle \sigma _{il}}$ are the average and standard deviation of the observed performance measures for objective $l$ of design $i$, and $N_{i}$ is the number of observations.

Thus, instead of maximizing ${\displaystyle \Pr\{CS\}}$, we can maximize its lower bound, i.e., ${\displaystyle APCS{-}M\equiv 1-ub_{1}-ub_{2}.}$ Assuming ${\displaystyle \tau \rightarrow \infty }$, the Lagrange method can be applied to conclude the following rules:

${\displaystyle \tau _{i}={\frac {\beta _{i}}{\sum _{j\in \Theta }\beta _{j}}}\tau ,}$

in which

• for a design ${\displaystyle h\in S_{A}}$, ${\displaystyle \beta _{h}={\frac {\left({\hat {\sigma }}_{hl_{j_{h}}^{h}}^{2}+{\hat {\sigma }}_{j_{h}l_{j_{h}}^{h}}^{2}/\rho _{h}\right)/{\delta _{hj_{h}l_{j_{h}}^{h}}^{2}}}{\left({\hat {\sigma }}_{ml_{jm}^{m}}^{2}+{\hat {\sigma }}_{j_{m}l_{jm}^{m}}^{2}/\rho _{m}\right)/{\delta _{mj_{m}l_{j_{m}}^{m}}^{2}}}}}$,
• for a design ${\displaystyle d\in S_{B}}$, ${\displaystyle \beta _{d}={\sqrt {\sum _{i\in \Theta _{d}^{*}}{\frac {\sigma _{dl_{d}^{i}}^{2}}{\sigma _{il_{d}^{i}}^{2}}}\beta _{i}^{2}}}}$,

and ${\displaystyle \delta _{ijl}={\bar {J}}_{jl}-{\bar {J}}_{il},}$

${\displaystyle j_{i}\equiv \arg \max _{j\in \Theta ,j\neq i}\prod _{l=1}^{H}{\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\}},}$

${\displaystyle l_{j_{i}}^{i}\equiv \arg \min _{l\in {1,\ldots ,H}}\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\},}$

${\displaystyle S_{A}\equiv \left\{design\;h\in S\mid {\frac {\delta _{hj_{h}l_{j_{h}}^{h}}^{2}}{{\frac {{\hat {\sigma }}_{hl_{j_{h}}^{h}}^{2}}{\alpha _{h}}}+{\frac {{\hat {\sigma }}_{j_{h}l_{j_{h}}^{h}}^{2}}{\alpha _{j_{h}}}}}}<\min _{i\in \Theta _{h}}{\frac {\delta _{ihl_{h}^{i}}^{2}}{{\frac {{\hat {\sigma }}_{il_{h}^{i}}^{2}}{\alpha _{i}}}+{\frac {{\hat {\sigma }}_{hl_{h}^{i}}^{2}}{\alpha _{h}}}}}\right\},}$

${\displaystyle S_{B}\equiv S\backslash S_{A},}$

${\displaystyle \Theta _{h}={i|i\in S,j_{i}=h},}$

${\displaystyle \Theta _{d}^{*}={h|h\in S_{A},j_{h}=d},}$

${\displaystyle \rho _{i}=\alpha _{j_{i}}/\alpha _{i}.}$

Optimal Computing Budget Allocation for Constrained Optimization

Similar to the previous section, there are many situations with multiple performance measures. If the multiple performance measures are equally important, the decision makers can use the MOCBA. In other situations, the decision makers have one primary performance measure to be optimized while the secondary performance measures are constrained by certain limits. The primary performance measure can be called the main objective while the secondary performance measures are referred as the constraint measures. This falls into the problem of constrained optimization. When the number of alternatives is fixed, the problem is called constrained ranking and selection where the goal is to select the best feasible design given that both the main objective and the constraint measures need to be estimated via stochastic simulation. The OCBA method for constrained optimization (called OCBA-CO) can be found in Pujowidianto et al. (2009) ^[11] and Lee et al. (2012).^[12]

The key change is in the definition of PCS. There are two components in constrained optimisation, namely optimality and feasibility. As a result, the simulation budget can be allocated to each non-best design either based on the optimality or feasibility. In other word, a non-best design will not be wrongly selected as the best feasible design if it remains either infeasible or worse than the true best feasible design. The idea is that it is not necessary to spend a large portion of the budget to determine the feasibility if the design is clearly worse than the best. Similarly, we can save the budget by allocating based on feasibility if the design is already better than the best in terms of the main objective.

Web-based demonstration of OCBA

The following link provides an OCBA demonstration using a simple example. In the demo, you will see how OCBA performs and allocates computing budget differently as compared with traditional equal allocation approach.

• http://seor.gmu.edu/~cchen9/OCBA/welcome.html

References

1. Fu, M, C. H. Chen, and L. Shi, “Some Topics for Simulation Optimization,” Proceedings of 2008 Winter Simulation Conference, pp. 27–38, Miami, FL, December 2008.
2. Chen, and Loo H. Lee. Stochastic simulation optimization an optimal computing budget allocation. Singapore Hackensack, NJ: World Scientific, 2011. Print..
3. Chen, C. H. "An Effective Approach to Smartly Allocate Computing Budget for Discrete Event Simulation," Proceedings of the 34th IEEE Conference on Decision and Control, pp. 2598–2605, December 1995.
4. Chen, Chun-Hung. "Optimal Computing Budget Allocation (OCBA) for Simulation-based Decision Making Under Uncertainty". Retrieved 9 July 2013.
5. Chen, and Loo H. Lee. Stochastic simulation optimization an optimal computing budget allocation. Singapore Hackensack, NJ: World Scientific, 2011. Print.
6. Chen, C. H., M. Fu, L. Shi, and L. H. Lee, “Stochastic Systems Simulation Optimization,” Frontiers of Electrical and Electronic Engineering in China, 6(3), 468–480, 2011
7. Szechtman R, Yücesan E (2008) A new perspective on feasibility determination. Proc of the 2008 Winter Simul Conf 273–280
8. Jia QS, Zhou E, Chen CH (2012). efficient computing budget allocation for finding simplest good designs. IIE Trans, To Appear.
9. Trailovic Tekin E, Sabuncuoglu I (2004) Simulation optimization: A comprehensive review on theory and applications. IIE Trans 36:1067–1081
10. Trailovic L, Pao LY (2004) Computing budget allocation for efficient ranking and selection of variances with application to target tracking algorithms, IEEE Trans Autom Control 49:58–67.
11. Pujowidianto NA, Lee LH, Chen CH, Yap CM (2009) Optimal computing budget allocation for constrained optimization. Proc of the 2009 Winter Simul Conf 584–589.
12. Lee LH, Pujowidianto NA, Li LW, Chen CH, Yap CM (2012) Approximation simulation budget allocation for selecting the best design in the presence of stochastic constraints, IEEE Trans Autom Control 57:2940–2945.

External links

• http://seor.gmu.edu/~cchen9/ocba.html
• Russian translation of OCBA page by Carschimp
• Ukrainian translation of OCBA page by sciposts