Home > Research > Publications & Outputs > Rapid Discrete Optimization via Simulation with...

Electronic data

  • SemelhagoNelsonSongWaechterIJoCAAM

    Accepted author manuscript, 924 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

Links

Text available via DOI:

View graph of relations

Rapid Discrete Optimization via Simulation with Gaussian Markov Random Fields

Research output: Contribution to journalJournal articlepeer-review

E-pub ahead of print
Close
<mark>Journal publication date</mark>14/10/2020
<mark>Journal</mark>INFORMS Journal on Computing
Volume0
Number of pages16
Pages (from-to)0-0
Publication StatusE-pub ahead of print
Early online date14/10/20
<mark>Original language</mark>English

Abstract

Inference-based optimization via simulation, which substitutes Gaussian
process (GP) learning for the structural properties exploited in mathematical programming,is a powerful paradigm that has been shown to be remarkably effective in problems of modest feasible-region size and decision-variable dimension. The limitation to “modest” problems is a result of the computational overhead and numerical challenges encountered in computing the GP conditional (posterior) distribution on each iteration. In this paper, we substantially expand the size of discrete-decision-variable optimization-via-simulation problems that can be attacked in this way by exploiting a particular GP—discrete Gaussian Markov random fields—and carefully tailored computational methods. The
result is the rapid Gaussian Markov Improvement Algorithm (rGMIA), an algorithm that delivers both a global convergence guarantee and finite-sample optimality-gap inference for significantly larger problems. Between infrequent evaluations of the global conditional distribution, rGMIA applies the full power of GP learning to rapidly search smaller sets of promising feasible solutions that need not be spatially close. We carefully document the computational savings via complexity analysis and an extensive empirical study.Summary of Contribution: The broad topic of the paper is optimization via simulation, which means optimizing some performance measure of a system that may only be estimated by executing a stochastic, discrete-event simulation. Stochastic simulation is a core topic and method of operations research. The focus of this paper is on significantly speeding-up the computations underlying an existing method that is based on Gaussian process learning, where the underlying Gaussian process is a discrete Gaussian Markov Random Field. This speed-up is accomplished by employing smart computational linear algebra, state-of-the-art algorithms, and a careful divide-and-conquer evaluation strategy.
Problems of significantly greater size than any other existing algorithm with similar guarantees can solve are solved as illustrations.