In computer science, optimal computing budget allocation (OCBA) is an approach to maximize the overall simulation efficiency for finding an optimal decision.[1] It was introduced in the mid-1990s by Dr. Chun-Hung Chen.
OCBA determines the number of replications or the simulation time that is needed in order to receive acceptable or 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]
OCBA has also been shown effective in enhancing partition-based random search algorithms for solving deterministic global optimization problems.[4]
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, OCBA focuses 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.[5]
For example, we can create a simple simulation between five 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.
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 τ.
\begin{align}
max | |
\tau1,\tau2,\ldots,\tauk |
&PCS\\ subjectto
k | |
&\sum | |
i=1 |
\taui=\tau,\\ &\taui\ge0,i=1,2,...,k. (1) \end{align}
In this case
k | |
\sum | |
i=1 |
\taui=\tau
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.[11]
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
\Pr\{CS\}\equiv\Pr\left\{\left(
cap | |
i\inSp |
Ei\right)cap\left(capip}
c | |
E | |
i |
\right)\right\},
in which
Sp
\overline{S}p
\overline{S}p=\Theta\backslashSp
Ei
i
c | |
E | |
i |
i
e1
e2
e1=1-\Pr\left\{capip}
c | |
E | |
i |
\right\}
e2=1-\Pr\left\{
cap | |
i\inSp |
Ei\right\}
Besides, it can be proven that
e1\lequb1=H\left|\overline{S}p\right|-H\sumip}{maxj\in\Theta,\left[minl
and
e2\lequb2=(k-1)
\sum | |
i\inSp |
maxj\in\Theta,j\left[minl\in{1,\ldots,H}\Pr\left\{\tilde{J}jl\leq\tilde{J}il\right\}\right],
where
H
\tilde{J}il
Normal\left(\bar{J}il,
| |||||||
Ni |
\right).
\bar{J}il
\sigmail
l
i
Ni
Thus, instead of maximizing
\Pr\{CS\}
APCS{-}M\equiv1-ub1-ub2.
\tau → infty
\taui=
\betai | |
\sumj\in\Theta\betaj |
\tau,
in which
h\inSA
\betah=
\left(\hat{\sigma | |
2 |
|
+
2 | |||||||||||||
\hat{\sigma} | |||||||||||||
|
/\rhoh\right)/
2 | |||||||||||||
{\delta | |||||||||||||
|
d\inSB
\betad=
\sqrt{\sum | |||||||||
|
| |||||||||||||
|
2} | |
\beta | |
i |
and
\deltaijl=\bar{J}jl-\bar{J}il,
ji\equiv\argmaxj\in\Theta,
H | |
\prod | |
l=1 |
{\Pr\left\{\tilde{J}jl\leq\tilde{J}il\right\}},
i | |
l | |
ji |
\equiv\argminl\in{1,\ldots,H
SA\equiv\left\{design h\inS\mid
| ||||||||||||||
|
{\alpha | ||||
|
|
SB\equivS\backslashSA,
\Thetah={i|i\inS,ji=h},
* | |
\Theta | |
d |
={h|h\inSA,jh=d},
\rhoi=
\alpha | |
ji |
/\alphai.
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) [12] and Lee et al. (2012).[13]
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.
The goal of this problem is to determine all the feasible designs from a finite set of design alternatives, where the feasible designs are defined as the designs with their performance measures satisfying specified control requirements(constraints). With all the feasible designs selected, the decision maker can easily make the final decision by incorporating other performance considerations (e.g., deterministic criteria, such as cost, or qualitative criteria which are difficult to mathematically evaluate). Although the feasibility determination problem involves stochastic constraints too, it is distinguished from the constrained optimization problems introduced above, in that it aims to identify all the feasible designs instead of the single best feasible one.
Define
k
m
cj
j
j=1,2,...,m
SA
SB
\mui,j
j
i
2 | |
\sigma | |
i,j |
j
i
\alphai
proportion of the total simulation budget allocated to design
i
\bar{X}i,j
sample mean of simulation samples of the
j
i
Suppose all the constraints are provided in form of
\mui,j\leqcj
i=1,2,...,k,j=1,2,...,m
\begin{align} PCS=P\left(cap | |
i\inSA |
m | |
(cap | |
j=1 |
(\bar{X}i,j\leqcj))\cap
cap | |
i\inSB |
m | |
(cup | |
j=1 |
(\bar{X}i,j>cj))\right), \end{align}
\begin{align}
max | |
\alpha1,\alpha2,\ldots,\alphak |
&PCS\\ subjectto
k | |
&\sum | |
i=1 |
\alphai=1,\\ &\alphai\geq0,i=1,2,...,k. \end{align}
Let
Ii,j(x)=
(x-\mui,j)2 | ||||||
|
ji\inargminj\in\{1,...,m\
\begin{align} | \alphai | = |
\alphai' |
| |||||||||||
|
,i,i'\in\{1,2,...,k\}. \end{align}
Intuitively speaking, the above allocation rule says that (1) for a feasible design, the dominant constraint is the most difficult one to be correctly detected among all the constraints; and (2) for an infeasible design, the dominant constraint is the easiest one to be correctly detected among all constraints.
The original OCBA maximizes the probability of correct selection (PCS) of the best design. In practice, another important measure is the expected opportunity cost (EOC), which quantifies how far away the mean of the selected design is from that of the real best. This measure is important because optimizing EOC not only maximizes the chance of selecting the best design but also ensures that the mean of the selected design is not too far from that of the best design, if it fails to find the best one. Compared to PCS, EOC penalizes a particularly bad choice more than a slightly incorrect selection, and is thus preferred by risk-neutral practitioners and decision makers.
Specifically, the expected opportunity cost is
\begin{align} EOC=El{T
k
t
l{T}
\mui
i
i=1,2,...,k
\deltai,j=\mui-\muj
The budget allocation problem with the EOC objective measure is given by Gao et al. (2017)[15]
\begin{align}
min | |
\alpha1,\alpha2,\ldots,\alphak |
&EOC\\ subjectto
k | |
&\sum | |
i=1 |
\alphai=1,\\ &\alphai\geq0,i=1,2,...,k, \end{align}
\alphai
i
\alphat\gg\alphai
i ≠ t
\begin{align} &
| |||||||
|
k | |
=\sum | |
i=1,i ≠ t |
| |||||||
|
,\\ &
\alphai | = | |
\alphaj |
| |||||||
|
,i ≠ j ≠ t, \end{align}
2 | |
\sigma | |
i |
i
An implicit assumption for the aforementioned OCBA methods is that the true input distributions and their parameters are known, while in practice, they are typically unknown and have to be estimated from limited historical data. This may lead to uncertainty in the estimated input distributions and their parameters, which might (severely) affect the quality of the selection. Assuming that the uncertainty set contains a finite number of scenarios for the underlying input distributions and parameters, Gao et al. (2017)[16] introduces a new OCBA approach by maximizing the probability of correctly selecting the best design under a fixed simulation budget, where the performance of a design is measured by its worst-case performance among all the possible scenarios in the uncertainty set.
The following link provides an OCBA demonstration using a simple example. In the demo, OCBA performs and allocates computing budget differently as compared with traditional equal allocation approach.