Optimal computing budget allocation

Last updated

In computer science, optimal computing budget allocation (OCBA) is an approach to maximize the overall simulation efficiency for finding an optimal decision. [1] It was introduced in the mid-1990s by Dr. Chun-Hung Chen.

Contents

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. [2] This is accomplished by using an asymptotic framework to analyze the structure of the optimal allocation. [3]

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

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

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

In this case stands for the total computational cost. [6]

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), [7] 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. [8]

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

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

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

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

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) [14]

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

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

where,

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

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

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

Related Research Articles

<span class="mw-page-title-main">Normal distribution</span> Probability distribution

In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is

<span class="mw-page-title-main">Pauli matrices</span> Matrices important in quantum mechanics and the study of spin

In mathematical physics and mathematics, the Pauli matrices are a set of three 2 × 2 complex matrices which are Hermitian, involutory and unitary. Usually indicated by the Greek letter sigma, they are occasionally denoted by tau when used in connection with isospin symmetries.

In probability theory, Chebyshev's inequality guarantees that, for a wide class of probability distributions, no more than a certain fraction of values can be more than a certain distance from the mean. Specifically, no more than 1/k2 of the distribution's values can be k or more standard deviations away from the mean. The rule is often called Chebyshev's theorem, about the range of standard deviations around the mean, in statistics. The inequality has great utility because it can be applied to any probability distribution in which the mean and variance are defined. For example, it can be used to prove the weak law of large numbers.

Linear elasticity is a mathematical model of how solid objects deform and become internally stressed due to prescribed loading conditions. It is a simplification of the more general nonlinear theory of elasticity and a branch of continuum mechanics.

In physics, the S-matrix or scattering matrix relates the initial state and the final state of a physical system undergoing a scattering process. It is used in quantum mechanics, scattering theory and quantum field theory (QFT).

<span class="mw-page-title-main">Hamilton–Jacobi equation</span> A reformulation of Newtons laws of motion using the calculus of variations

In physics, the Hamilton–Jacobi equation, named after William Rowan Hamilton and Carl Gustav Jacob Jacobi, is an alternative formulation of classical mechanics, equivalent to other formulations such as Newton's laws of motion, Lagrangian mechanics and Hamiltonian mechanics.

In differential topology, the jet bundle is a certain construction that makes a new smooth fiber bundle out of a given smooth fiber bundle. It makes it possible to write differential equations on sections of a fiber bundle in an invariant form. Jets may also be seen as the coordinate free versions of Taylor expansions.

Ridge regression is a method of estimating the coefficients of multiple-regression models in scenarios where the independent variables are highly correlated. It has been used in many fields including econometrics, chemistry, and engineering. Also known as Tikhonov regularization, named for Andrey Tikhonov, it is a method of regularization of ill-posed problems. It is particularly useful to mitigate the problem of multicollinearity in linear regression, which commonly occurs in models with large numbers of parameters. In general, the method provides improved efficiency in parameter estimation problems in exchange for a tolerable amount of bias.

In physics, the Polyakov action is an action of the two-dimensional conformal field theory describing the worldsheet of a string in string theory. It was introduced by Stanley Deser and Bruno Zumino and independently by L. Brink, P. Di Vecchia and P. S. Howe in 1976, and has become associated with Alexander Polyakov after he made use of it in quantizing the string in 1981. The action reads:

In abstract algebra, Hilbert's Theorem 90 (or Satz 90) is an important result on cyclic extensions of fields (or to one of its generalizations) that leads to Kummer theory. In its most basic form, it states that if L/K is an extension of fields with cyclic Galois group G = Gal(L/K) generated by an element and if is an element of L of relative norm 1, that is

Thermal shock is a phenomenon characterized by a rapid change in temperature that results in a transient mechanical load on an object. The load is caused by the differential expansion of different parts of the object due to the temperature change. This differential expansion can be understood in terms of strain, rather than stress. When the strain exceeds the tensile strength of the material, it can cause cracks to form and eventually lead to structural failure.

In physics, Larmor precession is the precession of the magnetic moment of an object about an external magnetic field. The phenomenon is conceptually similar to the precession of a tilted classical gyroscope in an external torque-exerting gravitational field. Objects with a magnetic moment also have angular momentum and effective internal electric current proportional to their angular momentum; these include electrons, protons, other fermions, many atomic and nuclear systems, as well as classical macroscopic systems. The external magnetic field exerts a torque on the magnetic moment,

<span class="mw-page-title-main">Newman–Penrose formalism</span> Notation in general relativity

The Newman–Penrose (NP) formalism is a set of notation developed by Ezra T. Newman and Roger Penrose for general relativity (GR). Their notation is an effort to treat general relativity in terms of spinor notation, which introduces complex forms of the usual variables used in GR. The NP formalism is itself a special case of the tetrad formalism, where the tensors of the theory are projected onto a complete vector basis at each point in spacetime. Usually this vector basis is chosen to reflect some symmetry of the spacetime, leading to simplified expressions for physical observables. In the case of the NP formalism, the vector basis chosen is a null tetrad: a set of four null vectors—two real, and a complex-conjugate pair. The two real members often asymptotically point radially inward and radially outward, and the formalism is well adapted to treatment of the propagation of radiation in curved spacetime. The Weyl scalars, derived from the Weyl tensor, are often used. In particular, it can be shown that one of these scalars— in the appropriate frame—encodes the outgoing gravitational radiation of an asymptotically flat system.

Expected shortfall (ES) is a risk measure—a concept used in the field of financial risk measurement to evaluate the market risk or credit risk of a portfolio. The "expected shortfall at q% level" is the expected return on the portfolio in the worst of cases. ES is an alternative to value at risk that is more sensitive to the shape of the tail of the loss distribution.

In computational chemistry, a constraint algorithm is a method for satisfying the Newtonian motion of a rigid body which consists of mass points. A restraint algorithm is used to ensure that the distance between mass points is maintained. The general steps involved are: (i) choose novel unconstrained coordinates, (ii) introduce explicit constraint forces, (iii) minimize constraint forces implicitly by the technique of Lagrange multipliers or projection methods.

Location estimation in wireless sensor networks is the problem of estimating the location of an object from a set of noisy measurements. These measurements are acquired in a distributed manner by a set of sensors.

<span class="mw-page-title-main">Fiber-reinforced composite</span>

A fiber-reinforced composite (FRC) is a composite building material that consists of three components:

  1. the fibers as the discontinuous or dispersed phase,
  2. the matrix as the continuous phase, and
  3. the fine interphase region, also known as the interface.
<span class="mw-page-title-main">Relativistic Lagrangian mechanics</span> Mathematical formulation of special and general relativity

In theoretical physics, relativistic Lagrangian mechanics is Lagrangian mechanics applied in the context of special relativity and general relativity.

In computational chemistry and molecular dynamics, the combination rules or combining rules are equations that provide the interaction energy between two dissimilar non-bonded atoms, usually for the part of the potential representing the van der Waals interaction. In the simulation of mixtures, the choice of combining rules can sometimes affect the outcome of the simulation.

The unified strength theory (UST). proposed by Yu Mao-Hong is a series of yield criteria and failure criteria. It is a generalized classical strength theory which can be used to describe the yielding or failure of material begins when the combination of principal stresses reaches a critical value.

References

  1. Fu, M, C. H. Chen, and L. Shi, “Some Topics for Simulation Optimization,” Proceedings of 2008 Winter Simulation Conference, pp. 27–38, Miami, FL, December 2008.
  2. Chen, and Loo H. Lee. Stochastic simulation optimization an optimal computing budget allocation. Singapore Hackensack, NJ: World Scientific, 2011. Print.
  3. Chen, C. H. "An Effective Approach to Smartly Allocate Computing Budget for Discrete Event Simulation," Proceedings of the 34th IEEE Conference on Decision and Control, pp. 2598–2605, December 1995.
  4. Chen, W., S. Gao, C. H. Chen and L. Shi, "An Optimal Sample Allocation Strategy for Partition-based Random Search," IEEE Transactions on Automation Science and Engineering, 11(1), 177–186, 2014.
  5. 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.
  6. Chen, and Loo H. Lee. Stochastic simulation optimization an optimal computing budget allocation. Singapore Hackensack, NJ: World Scientific, 2011. Print.
  7. Szechtman R, Yücesan E (2008) A new perspective on feasibility determination. Proc of the 2008 Winter Simul Conf 273–280
  8. Jia QS, Zhou E, Chen CH (2012). efficient computing budget allocation for finding simplest good designs. IIE Trans, To Appear.
  9. Trailovic Tekin E, Sabuncuoglu I (2004) Simulation optimization: A comprehensive review on theory and applications. IIE Trans 36:1067–1081
  10. 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.
  11. Chen, C. H., M. Fu, L. Shi, and L. H. Lee, “Stochastic Systems Simulation Optimization,” Frontiers of Electrical and Electronic Engineering in China, 6(3), 468–480, 2011
  12. 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.
  13. 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.
  14. Gao, S. and W. Chen, "Efficient feasibility determination with multiple performance measure constraints," IEEE Transactions on Automatic Control, 62, 113–122, 2017.
  15. Gao, S., W. Chen and L. Shi, "A New Budget Allocation Framework for the Expected Opportunity Cost," Operations Research, 63, 787–803, 2017.
  16. Gao, S., H. Xiao, E. Zhou and W. Chen, "Robust Ranking and Selection with Optimal Computing Budget Allocation," Automatica, 81, 30–36, 2017.