TITLE: Discrete Optimzation via Simulation using Gaussian Markov Random Fields

ABSTRACT:

We consider maximizing or minimizing the expected value of a stochastic performance measure that can be observed by running a dynamic, discrete-event simulation when the feasible solutions are defined by integer-ordered decision variables. Inventory sizing, call center staffing and manufacturing system design are common applications. Standard approaches are ranking and selection, which takes no advantage of spatial structure, and adaptive random search, which exploits it but in a heuristic way (“good solutions tend to be clustered”). Instead, we construct an optimization procedure built on discrete Gaussian Markov random fields (GMRFs). This enables computation of the expected improvement (EI) that could be obtained by running the simulation for any feasible solution. This computation can be numerically challenging; however, GMRFs are defined by their precision matrices which can be constructed to be sparse. Thus, we can use sparse matrix techniques to calculate expressions that involve the precision matrix. We also introduce a new EI criterion that incorporates the uncertainty in stochastic simulation by treating the value at the current optimal solution as a random variable.