Optimal computing budget allocation


Optimal computing budget allocation is an approach to maximize the overall simulation efficiency for finding an optimal decision. The concept was introduced in the mid-1990s by Dr. Chun-Hung Chen. Simply put, OCBA is an approach to simulation that will help determine 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, it 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 5 alternatives. The goal is to select an alternative with minimum average delay time. The figure below shows preliminary simulation results. It is clear to see that alternative 2 and 3 have a significantly lower delay time. In order to save computation cost 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.

Problem

The main objective of OCBA is to maximize the probability of correct selection. PCS is subject to the sampling budget of a given stage of sampling τ.
In this case 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, 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 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. 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 is the OCBA concept that applies to multi-objective problems. In a typical MOCBA, the PCS is defined as
in which
We notice that, the Type I error and Type II error for identifying a correct Pareto set are respectively
and.
Besides, it can be proven that
and
where is the number of objectives, and follows posterior distribution
Noted that and are the average and standard deviation of the observed performance measures for objective of design, and is the number of observations.
Thus, instead of maximizing, we can maximize its lower bound, i.e., Assuming, the Lagrange method can be applied to conclude the following rules:
in which
and

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 can be found in Pujowidianto et al. and Lee et al..
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
. With all the feasible designs selected, the decision maker can easily make the final decision by incorporating other performance considerations. 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
Suppose all the constraints are provided in form of,. The probability of correctly selecting all the feasible designs is
and the budget allocation problem for feasibility determination is given by Gao and Chen
Let and. The asymptotic optimal budget allocation rule is
Intuitively speaking, the above allocation rule says that for a feasible design, the dominant constraint is the most difficult one to be correctly detected among all the constraints; and 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 of the best design. In practice, another important measure is the expected opportunity cost, 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
where,
The budget allocation problem with the EOC objective measure is given by Gao et al.
where is the proportion of the total simulation budget allocated to design.
If we assume for all, the asymptotic optimal budget allocation rule for this problem is
where is the variance of the simulation samples of design. This allocation rule is the same as the asymptotic optimal solution of problem. 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 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. 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, you will see how OCBA performs and allocates computing budget differently as compared with traditional equal allocation approach.