We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Rapid Discrete Optimization via Simulation with Gaussian Markov Random Fields.
- Authors
Semelhago, Mark; Nelson, Barry L.; Song, Eunhye; Wächter, Andreas
- 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.
- Subjects
GAUSSIAN Markov random fields; MATHEMATICAL programming; ALGORITHMS; GAUSSIAN processes; RANDOM fields; OPERATIONS research; LINEAR algebra
- Publication
INFORMS Journal on Computing, 2021, Vol 33, Issue 3, p915
- ISSN
1091-9856
- Publication type
Article
- DOI
10.1287/ijoc.2020.0971