Gaussian Markov Random Fields for Discrete Optimization via Simulation: Framework and Algorithms

Peter L. Salemi (), Eunhye Song (), Barry L. Nelson () and Jeremy Staum ()
Additional contact information
Peter L. Salemi: The MITRE Corporation, McLean, Virginia 22102
Eunhye Song: Department of Industrial and Manufacturing Engineering, The Pennsylvania State University, University Park, Pennsylvania 16802
Barry L. Nelson: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208
Jeremy Staum: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208

Operations Research, 2019, vol. 67, issue 1, 250-266

Abstract: We consider optimizing the expected value of some performance measure of a dynamic stochastic simulation with a statistical guarantee for optimality when the decision variables are discrete , in particular, integer-ordered; the number of feasible solutions is large; and the model execution is too slow to simulate even a substantial fraction of them. Our goal is to create algorithms that stop searching when they can provide inference about the remaining optimality gap similar to the correct-selection guarantee of ranking and selection when it simulates all solutions. Further, our algorithm remains competitive with fixed-budget algorithms that search efficiently but do not provide such inference. To accomplish this we learn and exploit spatial relationships among the decision variables and objective function values using a Gaussian Markov random field (GMRF). Gaussian random fields on continuous domains are already used in deterministic and stochastic optimization because they facilitate the computation of measures, such as expected improvement, that balance exploration and exploitation. We show that GMRFs are particularly well suited to the discrete decision–variable problem, from both a modeling and a computational perspective. Specifically, GMRFs permit the definition of a sensible neighborhood structure, and they are defined by their precision matrices, which can be constructed to be sparse. Using this framework, we create both single and multiresolution algorithms, prove the asymptotic convergence of both, and evaluate their finite-time performance empirically.

Keywords: large-scale discrete optimization via simulation; inferential optimization; Gaussian Markov random fields (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/opre.2018.1778 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:1:p:250-266

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().