Optimal computing budget allocation: Difference between revisions

Revision as of 05:29, 15 December 2024

Revision as of 08:16, 15 December 2024

Line 1:

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.<ref name="Chen1995">{{cite conference | last=Chen | first=Chun-Hung | title=An Effective Approach to Smartly Allocate Computing Budget for Discrete Event Simulation | book-title=Proceedings of the 34th IEEE Conference on Decision and Control | year=1995 | pages=2598–2605 | url=https://ieeexplore.ieee.org/document/478890478499 | publisher=IEEE }} </ref><ref name="Chen2011">{{cite book | last1=Chen | first1=Chun-Hung | last2=Lee | first2=Loo H. | title=Stochastic Simulation Optimization: An Optimal Computing Budget Allocation | series=World Scientific Series on Nonlinear Science Series A | publisher=World Scientific | year=2011 | volume=82 | doi=10.1142/8355 | isbn=978-981-4383-38-7 | url=https://www.worldscientific.com/worldscibooks/10.1142/83557437?srsltid=AfmBOoqKrPtEAQwx9OAUZIJMIuye75kDLYKHtuoFV7_RhJAsW6O0DA8A#t=aboutBook }}</ref> 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.<ref name="Chen2014">{{cite journal | last1=Chen | first1=Wei | last2=Gao | first2=ShuSiyang | last3=Chen | first3=Chun-Hung | last4=Shi | first4=Lei | title=An Optimal Sample Allocation Strategy for Partition-Based Random Search | journal=IEEE Transactions on Automation Science and Engineering | year=2014 | volume=11 | issue=1 | pages=177–186 | doi=10.1109/TASE.2013.2249053 | doi-broken-date=15 December 2024 | url=https://ieeexplorewww.ieeeresearchgate.orgnet/documentprofile/6681450Siyang_Gao2/publication/260721040_An_Optimal_Sample_Allocation_Strategy_for_Partition-Based_Random_Search/links/582584b808aeb45b58927ed5/An-Optimal-Sample-Allocation-Strategy-for-Partition-Based-Random-Search.pdf | publisher=IEEE }}</ref> 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,<ref name="Lee2012">{{cite journal | last1=Lee | first1=Loo Hay | last2=Li | first2=Li Wei | last3=Chen | first3=Chun-Hung | last4=Yap | first4=C. M. | title=Approximation Simulation Budget Allocation for Selecting the Best Design in the Presence of Stochastic Constraints | journal=IEEE Transactions on Automatic Control | year=2012 | volume=57 | issue=12 | pages=2940–2945 | doi=10.1109/TAC.2012.2204478 | doi-broken-date=15 December 2024 | url=https://ieeexplore.ieee.org/document/5371030 }}</ref> feasibility determination,<ref name="Szechtman2008">{{cite conference | last1=Szechtman | first1=R. | last2=Yücesan | first2=E. | title=A New Perspective on Feasibility Determination | book-title=Proceedings of the 2008 Winter Simulation Conference | year=2008 | pages=273–280 | url=https://informs-sim.org/wsc08papers/005.pdf }}</ref> and constrained optimization.<ref name="Gao2017">{{cite journal | last1=Gao | first1=Shu | last2=Xiao | first2=Hongsheng | last3=Zhou | first3=Enlu | last4=Chen | first4=Wei | title=Robust Ranking and Selection with Optimal Computing Budget Allocation | journal=Automatica | year=2017 | volume=81 | pages=30–36 | doi=10.1016/j.automatica.2017.03.015 | url=https://www.sciencedirect.com/science/article/abs/pii/S0005109817301070 }}</ref>

== Intuitive Explanation ==

Line 48:

<math>N_i</math>: The number of simulation replications allocated to alternative <math>i</math>.

This formula ensures that alternatives with smaller performance gaps (<math>\delta_{1,i}</math>) or higher variances (<math>\sigma_i</math>) 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.<ref>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.</ref> Numerical results show that OCBA can achieve the same simulation quality with only one-tenth of the computational effort compared to traditional methods.<ref name="Chen2011">{{cite book | last1=Chen, C.| H.,first1=Chun-Hung and| L.last2=Lee | first2=Loo H. Lee,| title=Stochastic Simulation Optimization: An Optimal Computing Budget Allocation. | series=World Scientific, Series on Nonlinear Science Series A | publisher=World Scientific | year=2011 | volume=82 | url=https://www.worldscientific.com/worldscibooks/10.1142/7437?srsltid=AfmBOoqKrPtEAQwx9OAUZIJMIuye75kDLYKHtuoFV7_RhJAsW6O0DA8A#t=aboutBook }}</ref>

== Some extensions of OCBA ==

Line 56:

According to Szechtman and Yücesan (2008),<ref>Szechtman R, Yücesan E (2008) [https://calhoun.nps.edu/bitstream/handle/10945/38580/031.pdf?sequence=3 A new perspective on feasibility determination]. Proc of the 2008 Winter Simul Conf 273–280</ref> OCBA is also helpful in feasibility determination problems. This is where the decisions makers are only interested in differentiating [[Logical possibility|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.<ref>Jia QS, Zhou E, Chen CH (2012). [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3653338/ efficient computing budget allocation for finding simplest good designs]. IIE Trans, To Appear.</ref>

In addition, Trailovic<ref>Trailovic Tekin E, Sabuncuoglu I (2004) Simulation optimization: A comprehensive review on theory and applications. IIE Trans 36:1067–1081</ref> and Pao<ref>Trailovic L, Pao LY (2004) [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.15.1213&rep=rep1&type=pdf Computing budget allocation for efficient ranking and selection of variances with application to target tracking algorithms], IEEE Trans Autom Control 49:58–67.</ref> (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.<ref name="ChenChen2011">Chen,{{cite C.book H.,| M.last1=Chen Fu,| L.first1=Chun-Hung Shi,| andlast2=Lee L.| first2=Loo H. Lee,| “Stochastic Systemstitle=Stochastic Simulation Optimization,”: FrontiersAn ofOptimal ElectricalComputing andBudget ElectronicAllocation Engineering| inseries=World China,Scientific 6(3),Series 468–480,on Nonlinear Science Series A | publisher=World Scientific | year=2011 | volume=82 | url=https://www.worldscientific.com/worldscibooks/10.1142/7437?srsltid=AfmBOoqKrPtEAQwx9OAUZIJMIuye75kDLYKHtuoFV7_RhJAsW6O0DA8A#t=aboutBook }}</ref>

== Multi-Objective OCBA ==

Line 198:

* '''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.<ref>{{cite conference | last=Chen, | first=Chun-Hung. "| title=An Effective Approach to Smartly Allocate Computing Budget for Discrete Event Simulation." ''| book-title=Proceedings of the 34th IEEE Conference on Decision and Control'', | year=1995, pp.| pages=2598–2605, IEEE| url=https://ieeexplore.ieee.org/document/478499 | publisher=IEEE }} </ref>

* '''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.<ref name="Chen2011">{{cite book | last1=Chen, | first1=Chun-Hung, and| last2=Lee | first2=Loo H. Lee.| ''title=Stochastic Simulation Optimization: An Optimal Computing Budget Allocation''. | series=World Scientific, Series on Nonlinear Science Series A | publisher=World Scientific | year=2011 | volume=82 | url=https://www.worldscientific.com/worldscibooks/10.1142/7437?srsltid=AfmBOoqKrPtEAQwx9OAUZIJMIuye75kDLYKHtuoFV7_RhJAsW6O0DA8A#t=aboutBook }}</ref>

* '''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 methodapproach demonstratedmaximizes improvedthe performanceprobability inof complexcorrect decisionaction selection under limited sampling budgets by dynamically balancing exploration of less-makingsampled actions and exploitation of promising scenariosones.<ref>{{cite journal | last1=ZhangLi | first1=HYunchuan | last2=Fu | first2=Michael C. | last3=Xu | first3=Jie | title=OptimizingAn Optimal Computing Budget Allocation Tree PoliciesPolicy infor MCTSMonte withCarlo OCBATree Search | journal=SymmetryarXiv preprint | year=2020 | volume=112009 | issue=1012407 | pagesurl=1297 | doi=10https://arxiv.3390org/sym11101297 | doi-access=freeabs/2009.12407 }}</ref>

* '''Online Serving Systems:'''

** The DynamicDistributed ComputationAsynchronous AllocationOptimal FrameworkComputing Budget Allocation (DCAFDA-OCBA), introduced in 2020,framework applies OCBA principles toin allocatea computationalcloud resourcescomputing inenvironment onlinefor servingsimulation systems effectivelyoptimization. ThisBy frameworkutilizing hasidle beendocker deployedcontainers successfullyand enabling asynchronous execution of simulation tasks, DA-OCBA improves the efficiency of simulation optimization in large-scale applications,systems. suchThe asframework Taobao'sdemonstrates displaysignificant computational savings advertisingand systemscalability, achievingmaking significantit resourceparticularly savingsuseful whilein maintainingapplications performancesuch as cloud-based resource allocation systems.<ref>{{cite journal | last1=ChenWang | first1=C.Yu H.| last2=Tang | first2=Wei | last3=Yao | first3=Yan | last4=Zhu | first4=Fang | title=DynamicDA-OCBA: ComputationDistributed Asynchronous Optimal Computing Budget Allocation forAlgorithm Onlineof ServingSimulation SystemsOptimization Using OCBACloud Computing | journal=Symmetry | year=20202019 | volume=11 | issue=10 | pages=1297 | doi=10.3390/sym11101297 | doi-accessurl=freehttps://www.mdpi.com/2073-8994/11/10/1297 }}</ref>

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

Line 216:

=== 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. This integration reduces simulation costs while preserving decision quality.<ref>{{cite journal |last1=Huang |first1=E. |last2=Chen |first2=C. H. |year=2019 |title=Gaussian Mixture Models for Enhancing Multi-Fidelity Simulation Optimization |journal=IEEE Transactions on Automation Science and Engineering |volume=16 |issue=2 |pages=574–586}}</ref>

'''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.<ref>{{cite journal |last1=Peng |first1=Y. |last2=Xu |first2=J. |last3=Lee |first3=L. H. |last4=Hu |first4=J. |last5=Chen |first5=C. H. |title=Efficient Simulation Sampling Allocation Using Multifidelity Models |journal=IEEE Transactions on Automatic Control |year=2019 |volume=64 |issue=8 |pages=3156–3169 |doi=10.1109/TAC.2018.2886165 |url=https://ieeexplore.ieee.org/document/8571289 }}</ref>

'''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.<ref>{{cite journal | title=Optimizing Resource Allocation in Service Systems via Simulation: A Bayesian Formulation | journal=Production and Operations Management | year=2023 | doi=10.1111/poms.13825 | url=https://doi.org/10.1111/poms.13825 | last1=Chen | first1=Weiwei | last2=Gao | first2=Siyang | last3=Chen | first3=Wenjie | last4=Du | first4=Jianzhong | volume=32 | pages=65–81 }}</ref>

'''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.<ref>{{cite journal | title=Optimizing Resource Allocation in Service Systems via Simulation: A Bayesian Formulation | journal=Production and Operations Management | year=2023 | doi=10.1111/poms.13825 | url=https://doi.org/10.1111/poms.13825 | last1=Chen | first1=Weiwei | last2=Gao | first2=Siyang | last3=Chen | first3=Wenjie | last4=Du | first4=Jianzhong | volume=32 | pages=65–81 }}</ref> 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.<ref>{{cite journal | last1=Goodwin | first1=Timothy | last2=Xu | first2=Jie | last3=Celik | first3=Niyazi | last4=Chen | first4=Chun-Hung | title=Real-Time Digital Twin-Based Optimization with Predictive Simulation Learning | journal=Journal of Simulation | year=2024 | volume=18 | issue=1 | pages=47–64 | doi=10.1080/17477778.2022.2046520 | url=https://www.tandfonline.com/doi/full/10.1080/17477778.2022.2046520 }}</ref> 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.<ref>{{cite journal | last1=Gao | first1=Siyang | last2=Du | first2=Jianzhong | last3=Chen | first3=Chun-Hung | title=A Contextual Ranking and Selection Method for Personalized Medicine | journal=Manufacturing and Service Operations Management | year=2024 | volume=26 | issue=1 | pages=167–181 | doi=10.1287/msom.2022.0232 | url=https://pubsonline.informs.org/doi/10.1287/msom.2022.0232 }}</ref>

'''Enhanced Simulation Efficiency:''' ML models integrated with OCBA reduce simulation runs by up to 50%, focusing computational resources on critical alternatives. This improvement is particularly beneficial in high-dimensional optimization problems, where traditional methods are computationally prohibitive.<ref>{{cite journal | last1=Zhang | first1=S. | title=Evaluating Machine Learning Accuracy in Simulation-Based Optimization | journal=INFORMS Journal on Computing | year=2021 | volume=33 | issue=2 | pages=452–467 }}</ref>

The integration of ML and OCBA showcases a transformative potential to tackle complex, high-dimensional problems with exceptional efficiency, paving the way for groundbreaking research opportunities.