Discrete optimization via simulation using Gaussian Markov random fields

Peter Salemi, Barry L Nelson, Jeremy C Staum

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

We construct a discrete optimization via simulation (DOvS) procedure using discrete Gaussian Markov random fields (GMRFs). Gaussian random fields (GRFs) are used in DOvS to balance exploration and exploitation. They enable computation of the expected improvement (EI) due to running the simulation to evaluate a feasible point of the optimization problem. Existing methods use GRFs with a continuous domain, which leads to dense covariance matrices, and therefore can be ill-suited for large-scale problems due to slow and ill-conditioned numerical computations. The use of GMRFs leads to sparse precision matrices, on which several sparse matrix techniques can be applied. To allocate the simulation effort throughout the procedure, we introduce a new EI criterion that incorporates the uncertainty in stochastic simulation by treating the value at the current optimal point as a random variable.

Original languageEnglish (US)
Title of host publicationProceedings of the 2014 Winter Simulation Conference, WSC 2014
EditorsAndreas Tolk, Saikou Y. Diallo, Ilya O. Ryzhov, Levent Yilmaz
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3809-3820
Number of pages12
ISBN (Electronic)9781479974863
DOIs
StatePublished - Jan 23 2015
Event2014 Winter Simulation Conference, WSC 2014 - Savannah, United States
Duration: Dec 7 2014Dec 10 2014

Publication series

NameProceedings - Winter Simulation Conference
Volume2015-January
ISSN (Print)0891-7736

Other

Other2014 Winter Simulation Conference, WSC 2014
CountryUnited States
CitySavannah
Period12/7/1412/10/14

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Discrete optimization via simulation using Gaussian Markov random fields'. Together they form a unique fingerprint.

  • Cite this

    Salemi, P., Nelson, B. L., & Staum, J. C. (2015). Discrete optimization via simulation using Gaussian Markov random fields. In A. Tolk, S. Y. Diallo, I. O. Ryzhov, & L. Yilmaz (Eds.), Proceedings of the 2014 Winter Simulation Conference, WSC 2014 (pp. 3809-3820). [7020208] (Proceedings - Winter Simulation Conference; Vol. 2015-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/WSC.2014.7020208