In Computer Science, Optimal Computing Budget Allocation (OCBA) is a simulation optimization method designed to maximize the Probability of Correct Selection (PCS) while minimizing computational costs. First introduced by Dr. Chun-Hung Chen in the mid-1990s, OCBA determines how many simulation runs (or how much computational time) or the number of replications each design alternative needs to identify the best option while using as few resources as possible. OCBA has also been shown to enhance partition-based random search algorithms for solving deterministic global optimization problems. Over the years, OCBA has been applied in manufacturing systems design, healthcare planning, and financial modeling. It has also been extended to handle more complex scenarios, such as balancing multiple objectives, feasibility determination, and constrained optimization.
Intuitive Explanation The goal of OCBA is to provide a systematic approach to efficiently run a large number of simulations by focusing only on the critical alternatives, in order to select the best alternative. In other words, OCBA prioritizes only the most critical alternatives, minimizing computation time and reducing the variances of these critical estimators. The expected outcome is maintaining the required level of accuracy while requiring fewer computational resources.
Core Optimization Problem The problem is mathematically formulated as:
max τ 1 , τ 2 , … , τ k P C S {\displaystyle \max _{\tau _{1},\tau _{2},\ldots ,\tau _{k}}\mathrm {PCS} } Subject to:
∑ i = 1 k τ i = τ , τ i ≥ 0 , ; i = 1 , 2 , . . . , k {\displaystyle \sum _{i=1}^{k}\tau _{i}=\tau ,\quad \tau _{i}\geq 0,;i=1,2,...,k} where:
k {\displaystyle k} : Total number of design alternatives
τ i {\displaystyle \tau _{i}} : Number of simulation replications allocated to the i {\displaystyle i} -th design
τ {\displaystyle \tau } : Total computational budget OCBA optimizes the allocation of simulation replications by focusing on alternatives with higher variances or smaller performance gaps relative to the best alternative. The ratio of replications between two alternatives, such as N 2 {\displaystyle N_{2}} and N 3 {\displaystyle N_{3}} , is determined by the following formula:
N 2 N 3 = ( σ 2 δ 1 , 2 ) 2 ( σ 3 δ 1 , 3 ) 2 {\displaystyle {\frac {N_{2}}{N_{3}}}={\frac {\left({\frac {\sigma _{2}}{\delta _{1,2}}}\right)^{2}}{\left({\frac {\sigma _{3}}{\delta _{1,3}}}\right)^{2}}}}
Here:
σ i {\displaystyle \sigma _{i}} : The variance of the performance of alternative i {\displaystyle i} .
δ 1 , i {\displaystyle \delta _{1,i}} : The performance gap between the best alternative ( 1 {\displaystyle 1} ) and alternative i {\displaystyle i} .
… excerpt ends here. Continue reading the full article.
