Optimal computing budget allocation

Last updated

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. [1] [2]

Contents

OCBA has also been shown to enhance partition-based random search algorithms for solving deterministic global optimization problems. [3] 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, [4] feasibility determination, [5] and constrained optimization. [6]

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. [7]

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. Comparing 5 different alternatives with respect to Cost.png
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.

Core Optimization Problem

The problem is mathematically formulated as:

Subject to:

where:

: Total number of design alternatives

: Number of simulation replications allocated to the -th design

: 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 and , is determined by the following formula:

Here:

: The variance of the performance of alternative .

: The performance gap between the best alternative () and alternative .

: The number of simulation replications allocated to alternative .

This formula ensures that alternatives with smaller performance gaps () or higher variances () 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. [8] Numerical results show that OCBA can achieve the same simulation quality with only one-tenth of the computational effort compared to traditional methods. [2]

Some extensions of OCBA

According to Szechtman and Yücesan (2008), [9] 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. [10]

In addition, Trailovic [11] and Pao [12] (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. [2]

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

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

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

Feasibility determination

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 (2017) [15]

Let and . The asymptotic optimal budget allocation rule is

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

Specifically, the expected opportunity cost is

where,

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

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 (1). That is, asymptotically speaking, maximizing PCS and minimizing EOC are the same thing.

OCBA with input uncertainty

Assuming that the uncertainty set contains a finite number of scenarios for the underlying input distributions and parameters, Gao et al. (2017) [17] 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

Emerging Research Area: Integration of Machine Learning with OCBA

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. [22]

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. [23] 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. [24] 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. [25]

Sequential Allocation using Machine-learning Predictions as Light-weight Estimates (SAMPLE): SAMPLE is an extension of OCBA that presents a new opportunity for the integration of machine learning with digital twins for real-time simulation optimization and decision-making. Current methods for applying machine learning on simulation data may not produce the optimal solution due to errors encountered during the predictive learning phase since training data can be limited. SAMPLE overcomes this issue by leveraging lightweight machine learning models, which are easy to train and interpret, then running additional simulations once the real-world context is captured through the digital twin. [26]

References

  1. Chen, Chun-Hung (1995). "An Effective Approach to Smartly Allocate Computing Budget for Discrete Event Simulation". Proceedings of the 34th IEEE Conference on Decision and Control. IEEE. pp. 2598–2605.
  2. 1 2 3 4 Chen, Chun-Hung; Lee, Loo H. (2011). Stochastic Simulation Optimization: An Optimal Computing Budget Allocation. World Scientific Series on Nonlinear Science Series A. Vol. 82. World Scientific. doi:10.1142/7437. ISBN   978-981-4282-64-2.
  3. Chen, Wei; Gao, Siyang; Chen, Chun-Hung; Shi, Lei (2014). "An Optimal Sample Allocation Strategy for Partition-Based Random Search". IEEE Transactions on Automation Science and Engineering. 11 (1). IEEE: 177–186. Bibcode:2014ITASE..11..177C. doi:10.1109/TASE.2013.2251881.
  4. Lee, Loo Hay; Li, Li Wei; Chen, Chun-Hung; Yap, C. M. (2012). "Approximation Simulation Budget Allocation for Selecting the Best Design in the Presence of Stochastic Constraints". IEEE Transactions on Automatic Control. 57 (12): 2940–2945. doi:10.1109/TAC.2012.2204478 (inactive 28 January 2026).{{cite journal}}: CS1 maint: DOI inactive as of January 2026 (link)
  5. Szechtman, R.; Yücesan, E. (2008). "A New Perspective on Feasibility Determination" (PDF). Proceedings of the 2008 Winter Simulation Conference. pp. 273–280.
  6. Gao, Shu; Xiao, Hongsheng; Zhou, Enlu; Chen, Wei (2017). "Robust Ranking and Selection with Optimal Computing Budget Allocation". Automatica. 81: 30–36. doi:10.1016/j.automatica.2017.03.015.
  7. Chen, Chun-Hung. "Optimal Computing Budget Allocation (OCBA) for Simulation-based Decision Making Under Uncertainty". Archived from the original on 1 October 2013. Retrieved 9 July 2013.
  8. Chen, C. H., J. Lin, E. Yücesan, and S. E. Chick, "Simulation Budget Allocation for Further Enhancing the Efficiency of Ordinal Optimization," Journal of Discrete Event Dynamic Systems, 2000.
  9. Szechtman R, Yücesan E (2008) A new perspective on feasibility determination. Proc of the 2008 Winter Simul Conf 273–280
  10. Jia QS, Zhou E, Chen CH (2012). efficient computing budget allocation for finding simplest good designs. IIE Trans, To Appear.
  11. Trailovic Tekin E, Sabuncuoglu I (2004) Simulation optimization: A comprehensive review on theory and applications. IIE Trans 36:1067–1081
  12. Trailovic L, Pao LY (2004) Computing budget allocation for efficient ranking and selection of variances with application to target tracking algorithms, IEEE Trans Autom Control 49:58–67.
  13. Pujowidianto NA, Lee LH, Chen CH, Yap CM (2009) Optimal computing budget allocation for constrained optimization. Proc of the 2009 Winter Simul Conf 584–589.
  14. Lee LH, Pujowidianto NA, Li LW, Chen CH, Yap CM (2012) Approximation simulation budget allocation for selecting the best design in the presence of stochastic constraints, IEEE Trans Autom Control 57:2940–2945.
  15. Gao, S. and W. Chen, "Efficient feasibility determination with multiple performance measure constraints," IEEE Transactions on Automatic Control, 62, 113–122, 2017.
  16. Gao, Siyang; Chen, Weiwei; Shi, Leyuan (2017). "A New Budget Allocation Framework for the Expected Opportunity Cost" . Operations Research. 65 (3): 787–803. doi:10.1287/opre.2016.1581.
  17. Gao, S., H. Xiao, E. Zhou and W. Chen, "Robust Ranking and Selection with Optimal Computing Budget Allocation," Automatica, 81, 30–36, 2017.
  18. Chen, Chun-Hung (1995). "An Effective Approach to Smartly Allocate Computing Budget for Discrete Event Simulation". Proceedings of the 34th IEEE Conference on Decision and Control. IEEE. pp. 2598–2605.
  19. Li, Yunchuan; Fu, Michael C.; Xu, Jie (2020). "An Optimal Computing Budget Allocation Tree Policy for Monte Carlo Tree Search". IEEE Transactions on Automatic Control. 67 (6): 2685. arXiv: 2009.12407 . Bibcode:2022ITAC...67.2685L. doi:10.1109/TAC.2021.3088792.
  20. Wang, Yu; Tang, Wei; Yao, Yan; Zhu, Fang (2019). "DA-OCBA: Distributed Asynchronous Optimal Computing Budget Allocation Algorithm of Simulation Optimization Using Cloud Computing". Symmetry. 11 (10): 1297. Bibcode:2019Symm...11.1297W. doi: 10.3390/sym11101297 .
  21. Zhou, Chenhao; Xu, Jie; Miller-Hooks, Elise; Zhou, Weiwen; Chen, Chun-Hung; Lee, Loo Hay; Chew, Ek Peng; Li, Haobin (2021). "Analytics with digital-twinning: A decision support system for maintaining a resilient port". Decision Support Systems. 143 113496. doi:10.1016/j.dss.2021.113496.
  22. Peng, Y.; Xu, J.; Lee, L. H.; Hu, J.; Chen, C. H. (2019). "Efficient Simulation Sampling Allocation Using Multifidelity Models". IEEE Transactions on Automatic Control. 64 (8): 3156–3169. Bibcode:2019ITAC...64.3156P. doi:10.1109/TAC.2018.2886165.
  23. Chen, Weiwei; Gao, Siyang; Chen, Wenjie; Du, Jianzhong (2023). "Optimizing Resource Allocation in Service Systems via Simulation: A Bayesian Formulation". Production and Operations Management. 32: 65–81. doi: 10.1111/poms.13825 .
  24. Goodwin, Timothy; Xu, Jie; Celik, Niyazi; Chen, Chun-Hung (2024). "Real-Time Digital Twin-Based Optimization with Predictive Simulation Learning" . Journal of Simulation. 18 (1): 47–64. doi:10.1080/17477778.2022.2046520.
  25. Gao, Siyang; Du, Jianzhong; Chen, Chun-Hung (2024). "A Contextual Ranking and Selection Method for Personalized Medicine". Manufacturing and Service Operations Management. 26 (1): 167–181. arXiv: 2206.12640 . doi:10.1287/msom.2022.0232.
  26. Goodwin, Travis; Xu, Jie; Celik, Nurcin; Chen, Chun-Hung (2024). "Real-time digital twin-based optimization with predictive simulation learning". Journal of Simulation. 18: 47–64. doi:10.1080/17477778.2022.2046520.