Jump to content

Optimal computing budget allocation

Edit links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by ArticlesForCreationBot (talk | contribs) at 20:36, 27 August 2013 (Removing {{UserSpace draft}} from a page which is not in a userspace). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Optimal Computing Budget Allocation (OCBA) is a concept first introduced in the mid 1990’s 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.

Observing the above graphic, it is clear that alternative 2 and 3 have the lowest cost. OCBA suggests to run further simulations on only alternatives 2 and 3 in order to minimize computation cost


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 τ.

max_(τ_1,τ_2,…,τ_k ) PCS s.t. ∑_(i=1)^k τ_i=τ ≥0.----Equation 1

In this case ∑_(i=1)^k τ_i=τ 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 ration. 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: p1 + p2 = 31, p1 > 11 and p2 > 11.

Given this information we can see that there are 10 alternative computations (p1,p2). 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 .95 and .99 is compared using OCBA allocation and Equal Allocation.

PCS OCBA Equal Allocation
.95 470 1450
.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 algorything 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]

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.

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. ^ a b 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.


Retrieved from "https://en.wikipedia.org/w/index.php?title=Optimal_computing_budget_allocation&oldid=570444392"