Gaussian Markov Random Fields for Discrete Optimization via Simulation: Framework and Algorithms
Gaussian Markov Random Fields for Discrete Optimization via Simulation: Framework and Algorithms
复制标题
DOI：
10.1287/opre.2018.1778
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Peter L. Salemi;Eunhye Song;B. Nelson;J. Staum
中科院分区：
文献类型：
--
作者：
Peter L. Salemi;Eunhye Song;B. Nelson;J. Staum
本文为通过模拟将高斯马尔可夫随机场（GMRFs）用于离散决策变量优化奠定了基础；即优化模拟系统的性能。高斯过程在推理优化中已受到广泛应用，它迭代地更新模拟解的模型，并依靠该模型的统计推断来选择下一个要模拟的解。我们表明，对于离散问题，GMRFs（一种定义在图上的高斯过程）在剩余最优性差距方面比连续高斯过程的典型选择能提供更好的推断，从而使算法能够高效搜索，并在剩余最优性差距低于预定义阈值时正确停止。我们还针对大规模问题引入了多分辨率GMRFs的概念，不同分辨率的GMRFs通过相互作用可有效地将搜索聚焦在有希望的解区域上。
This paper lays the foundation for employing Gaussian Markov random fields (GMRFs) for discrete decision–variable optimization via simulation; that is, optimizing the performance of a simulated system. Gaussian processes have gained popularity for inferential optimization, which iteratively updates a model of the simulated solutions and selects the next solution to simulate by relying on statistical inference from that model. We show that, for a discrete problem, GMRFs, a type of Gaussian process defined on a graph, provides better inference on the remaining optimality gap than the typical choice of continuous Gaussian process and thereby enables the algorithm to search efficiently and stop correctly when the remaining optimality gap is below a predefined threshold. We also introduce the concept of multiresolution GMRFs for large-scale problems, with which GMRFs of different resolutions interact to efficiently focus the search on promising regions of solutions.