A principal reason underlying the importance of simulation optimization is that many real world problems in optimization are too complex to be given tractable mathematical formulations. Multiple nonlinearities, combinatorial relationships and uncertainties often render challenging practical problems inaccessible to modeling except by resorting to simulation – an outcome that poses grave difficulties for classical optimization methods.  In such situations, recourse is commonly made to itemizing a series of scenarios in the hope that at least one will give an acceptable solution.  Consequently, a long standing goal in both the optimization and simulation communities has been to create a way to guide a series of simulations to produce high quality solutions, in the absence of tractable mathematical structures.

Applications include the goals of finding:

• the best configuration of machines for production scheduling
• the best integration of manufacturing, inventory and distribution
• the best layouts, links and capacities for network design
• the best investment portfolio for financial, project, and product planning
• the best utilization of employees for workforce planning
• the best location of facilities for commercial distribution
• the best operating schedule for electrical power planning
• the best assignment of medical personnel in hospital administration
• the best setting of tolerances in manufacturing design
• the best set of treatment policies in waste management

and many other objectives.

Fu (2002) identifies 4 main approaches for optimizing simulations:

• stochastic approximation (gradient-based approaches)
• (sequential) response surface methodology
• random search
• sample path optimization (also known as stochastic counterpart)

Stochastic approximation algorithms attempt to mimic the gradient search method used in deterministic optimization.  The procedures based on this methodology must estimate the gradient of the objective function in order to determine a search direction.  Stochastic approximation targets continuous variable problems because of its close relationship with steepest descent gradient search.  However, this methodology has been applied to discrete problems (see e.g. Gerencsér, 1999).

Sequential response surface methodology is based on the principle of building metamodels, but it does so in a more localized way.  The “local response surface” is used to determine a search strategy (e.g., moving to the estimated gradient direction) and the process is repeated. In other words, the metamodels do not attempt to characterize the objective function in the entire solution space but rather concentrate in the local area that the search is currently exploring.

A random search method moves through the solution space by randomly selecting a point from the neighborhood of the current point.  This implies that a neighborhood must be defined as part of developing a random search algorithm.  Random search has been applied mainly to discrete problems and its appeal is based on the existence of theoretical convergence proofs.  Unfortunately, these theoretical convergence results mean little in practice where it’s more important to find high quality solutions within a reasonable length of time than to guarantee convergence to the optimum in a n infinite number of steps.

Sample path optimization is a methodology that exploits the knowledge and experience developed for deterministic continuous optimization problems.  The idea is to optimize a deterministic function that is based on n random variables, where n is the size of the sample path.  In the simulation context, the method of common random numbers is used to provide the same sample path to calculate the response over different values of the input factors.  Sample path optimization owes its name to the fact that the estimated optimal solution that it finds is based on a deterministic function built with one sample path obtained with a simulation model.  Generally, n needs to be large for the approximating optimization problem to be close to the original optimization problem (Andradóttir, 1998).

While these four approaches account for most of the literature in simulation optimization, they have not been used to develop optimization for simulation software.  Fu (2002) identifies only one case (SIMUL8’s OPTIMZ) where a procedure similar to a response surface method has been used in a commercial simulation package. 

Since Fu’s article was published, however, SIMUL8 has abandoned the use of OPTIMZ, bringing down to zero the number of practical applications of the four methods mentioned above.  Andradóttir (1998) gives the following explanation for the lack of practical (commercial) implementations of the methods mentioned above:

“Although simulation optimization has received a fair amount of attention from the research community in recent years, the current methods generally require a considerable amount of technical sophistication on the part of the user, and they often require a substantial amount of computer time as well.”

Leading commercial simulation software employs metaheuristics as the methodology of choice to provide optimization capabilities to their users. 

Nowadays nearly every commercial discrete-event or Monte Carlo simulation software package contains an optimization module that performs some sort of search for optimal values of input parameters rather than just performs pure statistical estimation.  This is a significant change from 1990 when none of the packages included such a functionality.

Like other developments in the Operations Research/Computer Science interface (e.g., those associated with solving large combinatorial optimization problems) commercial implementations of simulation optimization procedures have only become practical with the exponential increase of computational power and the advance in metaheuristic research.  The metaheuristic approach to simulation optimization is based on viewing the simulation model as a black box function evaluator.

Figure 1 shows the black-box approach to simulation optimization favored by procedures based on metaheuristic methodology.  In this approach, the metaheuristic optimizer chooses a set of values for the input parameters (i.e., factors or decision variables) and uses the responses generated by the simulation model to make decisions regarding the selection of the next trial solution.

Most of the optimization engines embedded in commercial simulation software are based on evolutionary approaches.  The most notable exception is the optimization algorithm in WITNESS, which is based on search strategies from simulated annealing and tabu search.  Evolutionary approaches search the solution space by building and then evolving a population of solutions.  The evolution is achieved by means of mechanisms that create new trials solutions out of the combination of two or more solutions that are in the current population.  Transformation of a single solution into a new trial solution is also considered in these approaches.  Examples of evolutionary approaches utilized in commercial software are shown in Table 1.

Table 1: Commercial Implementations of Evolutionary Approaches to Simulation Optimization

We have enclosed Tabu Search in parentheses following the listing of Scatter Search because these two methods derive from common origins and are frequently coupled, as they are in OptQuest. (See Glover, Laguna and Marti, 2003.) The main advantage of evolutionary approaches in general over those based primarily on sampling the neighborhood of a single solution (e.g., simulated annealing) is that they are capable of exploring a larger area of the solution space with a smaller number of objective function evaluations, provided they are implemented effectively.  Since in the context of simulation optimization evaluating the objective function entails running the simulation model, being able to find high quality solutions early in the search is of critical importance.  A procedure based on exploring neighborhoods would be effective if the starting point is a solution that is “close” to high quality solutions and if theses solutions can be reached by the move mechanism that defines the neighborhood.