Optimal computing budget allocation

In computer science, optimal computing budget allocation (OCBA) is an approach to maximize the overall simulation efficiency for finding an optimal decision. 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. This is accomplished by using an asymptotic framework to analyze the structure of the optimal allocation.

OCBA has also been shown effective in enhancing partition-based random search algorithms for solving deterministic global optimization problems.

Intuitive explanation

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.

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.

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

Problem

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{aligned}\max _{\tau _{1},\tau _{2},\ldots ,\tau _{k}}&\mathrm {PCS} \\{\text{subject to }}&\sum _{i=1}^{k}\tau _{i}=\tau ,\\&\tau _{i}\geq 0,i=1,2,...,k.\qquad (1)\end{aligned}}$

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

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), 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.

In addition, Trailovic and Pao (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.

Multi-objective OCBA

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(\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,
• ${\overline {S}}_{p}$ is the non-Pareto set, i.e., ${\overline {S}}_{p}=\Theta \backslash S_{p}$,
• $E_{i}$ is the event that design $i$ is non-dominated by all other designs,
• $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

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

Besides, it can be proven that

$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

$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 ${\tilde {J}}_{il}$ follows posterior distribution $Normal\left({\bar {J}}_{il},{\frac {\sigma _{il}^{2}}{N_{i}}}\right).$ Noted that ${\bar {J}}_{il}$ and $\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 $\Pr\{CS\}$, we can maximize its lower bound, i.e., $APCS{-}M\equiv 1-ub_{1}-ub_{2}.$ Assuming $\tau \rightarrow \infty$, the Lagrange method can be applied to conclude the following rules:

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

in which

• for a design $h\in S_{A}$, $\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 $d\in S_{B}$, $\beta _{d}={\sqrt {\sum _{i\in \Theta _{d}^{*}}{\frac {\sigma _{dl_{d}^{i}}^{2}}{\sigma _{il_{d}^{i}}^{2}}}\beta _{i}^{2}}}$,

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

$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\}},$

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

$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\},$

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

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

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

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

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) and Lee et al. (2012).

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.

Feasibility determination

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$: total number of designs;
• $m$: total number of performance measure constraints;
• $c_{j}$: control requirement of the $j$th constraint for all the designs, $j=1,2,...,m$;
• $S_{A}$: set of feasible designs;
• $S_{B}$: set of infeasible designs;
• $\mu _{i,j}$: mean of simulation samples of the $j$th constraint measure and design $i$;
• $\sigma _{i,j}^{2}$: variance of simulation samples of the $j$th constraint measure and design $i$;
• $\alpha _{i}$: proportion of the total simulation budget allocated to design $i$;
• ${\bar {X}}_{i,j}$: sample mean of simulation samples of the $j$th constraint measure and design $i$.

Suppose all the constraints are provided in form of $\mu _{i,j}\leq c_{j}$, $i=1,2,...,k,j=1,2,...,m$. The probability of correctly selecting all the feasible designs is

${\begin{aligned}\mathrm {PCS} =\mathbb {P} \left(\bigcap _{i\in S_{A}}{\Big (}\bigcap _{j=1}^{m}({\bar {X}}_{i,j}\leq c_{j}){\Big )}\cap \bigcap _{i\in S_{B}}{\Big (}\bigcup _{j=1}^{m}({\bar {X}}_{i,j}>c_{j}){\Big )}\right),\end{aligned}}$

and the budget allocation problem for feasibility determination is given by Gao and Chen (2017)

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

Let $I_{i,j}(x)={\frac {(x-\mu _{i,j})^{2}}{2\sigma _{i,j}^{2}}}$ and $j_{i}\in \mathrm {argmin} _{j\in \{1,...,m\}}I_{i,j}(c_{j})$. The asymptotic optimal budget allocation rule is

${\begin{aligned}{\frac {\alpha _{i}}{\alpha _{i'}}}={\frac {I_{i',j_{i'}}(c_{j_{i'}})}{I_{i,j_{i}}(c_{j_{i}})}},i,i'\in \{1,2,...,k\}.\end{aligned}}$

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.

OCBA with expected opportunity cost

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{aligned}EOC=\mathbb {E} _{\mathcal {T}}[\mu _{\mathcal {T}}-\mu _{t}]=\sum _{i=1,i\neq t}^{k}\delta _{i,t}\mathbb {P} ({\mathcal {T}}=i),\end{aligned}}$

where,

• $k$ is the total number of designs;
• $t$ is the real best design;
• ${\mathcal {T}}$ is the random variable whose realization is the observed best design;
• $\mu _{i}$ is the mean of the simulation samples of design $i$, $i=1,2,...,k$;
• $\delta _{i,j}=\mu _{i}-\mu _{j}$.

The budget allocation problem with the EOC objective measure is given by Gao et al. (2017)

${\begin{aligned}\min _{\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}&\mathrm {EOC} \\{\text{subject to }}&\sum _{i=1}^{k}\alpha _{i}=1,\\&\alpha _{i}\geq 0,i=1,2,...,k,\end{aligned}}$

where $\alpha _{i}$ is the proportion of the total simulation budget allocated to design $i$. If we assume $\alpha _{t}\gg \alpha _{i}$ for all $i\neq t$, the asymptotic optimal budget allocation rule for this problem is

${\begin{aligned}&{\frac {\alpha _{t}^{2}}{\sigma _{t}^{2}}}=\sum _{i=1,i\neq t}^{k}{\frac {\alpha _{i}^{2}}{\sigma _{i}^{2}}},\\&{\frac {\alpha _{i}}{\alpha _{j}}}={\frac {\sigma _{i}^{2}/\delta _{i,t}^{2}}{\sigma _{j}^{2}/\delta _{j,t}^{2}}},i\neq j\neq t,\end{aligned}}$

where $\sigma _{i}^{2}$ is the variance of the simulation samples of design $i$. This allocation rule is the same as the asymptotic optimal solution of problem (1). That is, asymptotically speaking, maximizing PCS and minimizing EOC are the same thing.

OCBA with input uncertainty

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

Web-based demonstration of OCBA

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.

External links

• Optimal Computing Budget Allocation (OCBA) for Simulation-based Decision Making Under Uncertainty (Simulation Optimization)