Optimal computing budget allocation

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. It works by focusing more on alternatives that are harder to evaluate, such as those with higher uncertainty or close performance to the best option.

Simply put, OCBA ensures that computational resources are distributed efficiently by allocating more simulation effort to design alternatives that are harder to evaluate or more likely to be the best. This allows researchers and decision-makers to achieve accurate results faster and with fewer resources.

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.

Figure 1: Preliminary simulation results show alternatives 2 and 3 have lower average delay times. OCBA suggests focusing further simulation resources on alternatives 2 and 3 while stopping simulations for alternatives 1, 4, and 5 to save costs without compromising accuracy.

For example, consider a simulation involving five alternatives, where the goal is to select the one with the minimum average delay time. Figure 1, shows preliminary simulation results (i.e., having run only a fraction of the required number of simulation replications). Alternatives 2 and 3 clearly have significantly lower delay times (highlighted in red). To save computation cost—which includes time, resources, and money spent on running simulations—OCBA suggests that more replications should be allocated to alternatives 2 and 3, while simulations for alternatives 1, 4, and 5 can be stopped much earlier without compromising accuracy.

Core Optimization Problem

Simulation is widely used for designing large, complex, stochastic systems, where analytical solutions are often infeasible. However, simulations can be computationally expensive because multiple simulation runs are needed to account for stochastic variability. The challenge lies in efficiently allocating limited computational resources to identify the best design alternative with high confidence.

The primary objective of OCBA is to maximize the Probability of Correct Selection (PCS), which represents the likelihood of identifying the best-performing design alternative among a finite set of options. This goal must be achieved while adhering to a limited computational budget. PCS is calculated based on the number of simulation replications allocated to each design.

The problem is mathematically formulated as:

$$\max _{\tau _{1},\tau _{2},\ldots ,\tau _{k}}\mathrm {PCS}$$

Subject to:

$\sum _{i=1}^{k}\tau _{i}=\tau ,\quad \tau _{i}\geq 0,;i=1,2,...,k$

where:

$k$: Total number of design alternatives

$\tau _{i}$: Number of simulation replications allocated to the $i$-th design

$\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}$ and $N_{3}$, is determined by the following formula:

$${\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:

$\sigma _{i}$: The variance of the performance of alternative $i$.

$\delta _{1,i}$: The performance gap between the best alternative ($1$) and alternative $i$.

$N_{i}$: The number of simulation replications allocated to alternative $i$.

This formula ensures that alternatives with smaller performance gaps ($\delta _{1,i}$) or higher variances ($\sigma _{i}$) receive more simulation replications. This maximizes computational efficiency while maintaining a high Probability of Correct Selection (PCS), ensuring computational efficiency by reducing replications for non-critical alternatives and increasing them for critical ones. Numerical results show that OCBA can achieve the same simulation quality with only one-tenth of the computational effort compared to traditional methods.

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.

Recent Applications of OCBA

Optimal Computing Budget Allocation (OCBA), has continued to evolve, demonstrating its adaptability and efficiency in addressing complex decision-making problems across various domains.

• Simulation-Based Ranking and Selection:
  • A 2023 study introduced a budget-adaptive allocation rule for OCBA, dynamically adjusting simulation budgets to maximize the probability of correct selection. This approach was validated through synthetic examples and case studies, showcasing its efficiency in identifying optimal system designs.

• Data-Driven Decision Making:
  • In 2022, researchers developed a data-driven OCBA method that addresses input uncertainty by updating distribution estimates with streaming data. This method ensures consistent and asymptotically optimal selection of the best design, enhancing decision-making in dynamic environments.

• Monte Carlo Tree Search (MCTS):
  • A 2020 study proposed an OCBA-based tree policy for MCTS, optimizing computational resource allocation to maximize the probability of correct action selection. This approach maximizes the probability of correct action selection under limited sampling budgets by dynamically balancing exploration of less-sampled actions and exploitation of promising ones.

• Online Serving Systems:
  • The Distributed Asynchronous Optimal Computing Budget Allocation (DA-OCBA) framework applies OCBA principles in a cloud computing environment for simulation optimization. By utilizing idle docker containers and enabling asynchronous execution of simulation tasks, DA-OCBA improves the efficiency of simulation optimization in large-scale systems. The framework demonstrates significant computational savings and scalability, making it particularly useful in applications such as cloud-based resource allocation systems.

These recent innovations demonstrate OCBA's growing versatility and effectiveness in optimizing resource allocation for diverse applications.

Emerging Research Area: Integration of Machine Learning with OCBA

The integration of Machine Learning (ML) with Optimal Computing Budget Allocation (OCBA) represents a promising area of research, leveraging ML’s predictive capabilities to enhance the efficiency and accuracy of simulation optimization. By incorporating ML models, OCBA can dynamically adapt resource allocation strategies, addressing complex decision-making problems with greater computational efficiency.

Applications

Predictive Multi-Fidelity Models: Gaussian Mixture Models (GMMs) predict relationships between low- and high-fidelity simulations, enabling OCBA to focus on the most promising alternatives. Multi-fidelity models combine insights from low-fidelity simulations, which are computationally inexpensive but less accurate, and high-fidelity simulations, which are more accurate but computationally intensive. The integration of GMMs into this process allows OCBA to strategically allocate computational resources across fidelity levels, significantly reducing simulation costs while maintaining decision accuracy.

Dynamic Resource Allocation in Healthcare: A Bayesian OCBA framework has been applied to allocate resources in hospital emergency departments, balancing service quality with operational efficiency. By minimizing expected opportunity costs, this approach supports real-time decision-making in high-stakes environments. Additionally, the integration of OCBA with real-time digital twin-based optimization has further advanced its application in predictive simulation learning, enabling dynamic adjustments to resource allocation in healthcare settings. Furthermore, a contextual ranking and selection method for personalized medicine leverages OCBA to optimize resource allocation in treatments tailored to individual patient profiles, demonstrating its potential in personalized healthcare.

External links

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