Gaussian markov random fields for discrete optimization via simulation: Framework and algorithms

Peter L. Salemi, Eunhye Song, Barry L. Nelson, Jeremy Staum

Research output: Contribution to journalArticle

1 Citation (Scopus)

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.

Original languageEnglish (US)
Pages (from-to)250-266
Number of pages17
JournalOperations Research
Volume67
Issue number1
DOIs
StatePublished - Jan 2019

Fingerprint

Random field
Simulation optimization
Optimality
Inference
Guarantee
Ranking and selection
Expected value
Performance measures
Exploration and exploitation
Modeling
Stochastic simulation
Integer
Stochastic optimization
Objective function

Keywords

  • Gaussian Markov random fields
  • Inferential optimization
  • Large-scale discrete optimization via simulation

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Cite this

Salemi, Peter L. ; Song, Eunhye ; Nelson, Barry L. ; Staum, Jeremy. / Gaussian markov random fields for discrete optimization via simulation : Framework and algorithms. In: Operations Research. 2019 ; Vol. 67, No. 1. pp. 250-266.
@article{96cbf1ff39984b94add5be777717a3af,
title = "Gaussian markov random fields for discrete optimization via simulation: Framework and algorithms",
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 = "Gaussian Markov random fields, Inferential optimization, Large-scale discrete optimization via simulation",
author = "Salemi, {Peter L.} and Eunhye Song and Nelson, {Barry L.} and Jeremy Staum",
year = "2019",
month = "1",
doi = "10.1287/opre.2018.1778",
language = "English (US)",
volume = "67",
pages = "250--266",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "1",

}

Gaussian markov random fields for discrete optimization via simulation : Framework and algorithms. / Salemi, Peter L.; Song, Eunhye; Nelson, Barry L.; Staum, Jeremy.

In: Operations Research, Vol. 67, No. 1, 01.2019, p. 250-266.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Gaussian markov random fields for discrete optimization via simulation

T2 - Framework and algorithms

AU - Salemi, Peter L.

AU - Song, Eunhye

AU - Nelson, Barry L.

AU - Staum, Jeremy

PY - 2019/1

Y1 - 2019/1

N2 - 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.

AB - 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.

KW - Gaussian Markov random fields

KW - Inferential optimization

KW - Large-scale discrete optimization via simulation

UR - http://www.scopus.com/inward/record.url?scp=85060582018&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85060582018&partnerID=8YFLogxK

U2 - 10.1287/opre.2018.1778

DO - 10.1287/opre.2018.1778

M3 - Article

AN - SCOPUS:85060582018

VL - 67

SP - 250

EP - 266

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 1

ER -