{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T00:39:49Z","timestamp":1768091989436,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,16]],"date-time":"2024-05-16T00:00:00Z","timestamp":1715817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["DMS-1854659, and CMMI-2045400"],"award-info":[{"award-number":["DMS-1854659, and CMMI-2045400"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"<jats:p>This article considers a discrete optimization via simulation (DOvS) problem defined on a graph embedded in the high-dimensional integer grid. Several DOvS algorithms that model the responses at the solutions as a realization of a Gaussian Markov random field (GMRF) have been proposed exploiting its inferential power and computational benefits. However, the computational cost of inference increases exponentially in dimension. We propose the projected Gaussian Markov improvement algorithm (pGMIA), which projects the solution space onto a lower-dimensional space creating the region-layer graph to reduce the cost of inference. Each node on the region-layer graph can be mapped to a set of solutions projected to the node; these solutions form a lower-dimensional solution-layer graph. We define the response at each region-layer node to be the average of the responses within the corresponding solution-layer graph. From this relation, we derive the region-layer GMRF to model the region-layer responses. The pGMIA alternates between the two layers to make a sampling decision at each iteration. It first selects a region-layer node based on the lower-resolution inference provided by the region-layer GMRF, then makes a sampling decision among the solutions within the solution-layer graph of the node based on the higher-resolution inference from the solution-layer GMRF. To solve even higher-dimensional problems (e.g., 100 dimensions), we also propose the pGMIA+: a multi-layer extension of the pGMIA. We show that both pGMIA and pGMIA+ converge to the optimum almost surely asymptotically and empirically demonstrate their competitiveness against state-of-the-art high-dimensional Bayesian optimization algorithms.<\/jats:p>","DOI":"10.1145\/3649463","type":"journal-article","created":{"date-parts":[[2024,3,1]],"date-time":"2024-03-01T12:09:55Z","timestamp":1709294995000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Projected Gaussian Markov Improvement Algorithm for High-Dimensional Discrete Optimization via Simulation"],"prefix":"10.1145","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-6647-2073","authenticated-orcid":false,"given":"Xinru","family":"Li","sequence":"first","affiliation":[{"name":"General Motors Corp, Warren, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5171-0614","authenticated-orcid":false,"given":"Eunhye","family":"Song","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,16]]},"reference":[{"key":"e_1_3_3_2_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning","author":"Baptista Ricardo","year":"2018","unstructured":"Ricardo Baptista and Matthias Poloczek. 2018. Bayesian optimization of combinatorial structures. In Proceedings of the 35th International Conference on Machine Learning."},{"issue":"1","key":"e_1_3_3_3_1","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s10898-019-00839-1","article-title":"On the choice of the low-dimensional domain for global optimization via random embeddings","volume":"76","author":"Binois Micka\u00ebl","year":"2020","unstructured":"Micka\u00ebl Binois, David Ginsbourger, and Olivier Roustant. 2020. On the choice of the low-dimensional domain for global optimization via random embeddings. Journal of Global Optimization 76, 1 (2020), 69\u201390.","journal-title":"Journal of Global Optimization"},{"issue":"2","key":"e_1_3_3_4_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3545611","article-title":"A survey on high-dimensional Gaussian process modeling with application to Bayesian optimization","volume":"2","author":"Binois Micka\u00ebl","year":"2022","unstructured":"Micka\u00ebl Binois and Nathan Wycoff. 2022. A survey on high-dimensional Gaussian process modeling with application to Bayesian optimization. ACM Transactions on Evolutionary Learning and Optimization 2, 2 (2022), 1\u201326.","journal-title":"ACM Transactions on Evolutionary Learning and Optimization"},{"issue":"5","key":"e_1_3_3_5_1","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1177\/0272989X15611359","article-title":"Using active learning for speeding up calibration in simulation models","volume":"36","author":"Cevik Mucahit","year":"2016","unstructured":"Mucahit Cevik, Mehmet Ali Ergun, Natasha K. Stout, Amy Trentham-Dietz, Mark Craven, and Oguzhan Alagoz. 2016. Using active learning for speeding up calibration in simulation models. Medical Decision Making 36, 5 (2016), 581\u2013593.","journal-title":"Medical Decision Making"},{"key":"e_1_3_3_6_1","volume-title":"Sampling Techniques","author":"Cochran William Gemmell","year":"1977","unstructured":"William Gemmell Cochran. 1977. Sampling Techniques. New York: Wiley."},{"issue":"7","key":"e_1_3_3_7_1","doi-asserted-by":"crossref","first-page":"1283","DOI":"10.1080\/00949655.2014.945932","article-title":"Global sensitivity analysis with dependence measures","volume":"85","author":"Veiga Sebastien Da","year":"2015","unstructured":"Sebastien Da Veiga. 2015. Global sensitivity analysis with dependence measures. Journal of Statistical Computation and Simulation 85, 7 (2015), 1283\u20131305.","journal-title":"Journal of Statistical Computation and Simulation"},{"key":"e_1_3_3_8_1","first-page":"1025","volume-title":"Advances in Neural Information Processing Systems","author":"Djolonga Josip","year":"2013","unstructured":"Josip Djolonga, Andreas Krause, and Volkan Cevher. 2013. High-dimensional Gaussian process bandits. In Advances in Neural Information Processing Systems. 1025\u20131033."},{"key":"e_1_3_3_9_1","first-page":"493","volume-title":"Uncertainty in Artificial Intelligence","author":"Eriksson David","year":"2021","unstructured":"David Eriksson and Martin Jankowiak. 2021. High-dimensional Bayesian optimization with sparse axis-aligned subspaces. In Uncertainty in Artificial Intelligence. PMLR, 493\u2013503."},{"key":"e_1_3_3_10_1","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.neucom.2019.11.004","article-title":"Dealing with categorical and integer-valued variables in Bayesian optimization with Gaussian processes","volume":"380","author":"Garrido-Merch\u00e1n Eduardo C.","year":"2020","unstructured":"Eduardo C. Garrido-Merch\u00e1n and Daniel Hern\u00e1ndez-Lobato. 2020. Dealing with categorical and integer-valued variables in Bayesian optimization with Gaussian processes. Neurocomput. 380, C (2020), 20\u201335.","journal-title":"Neurocomput."},{"key":"e_1_3_3_11_1","first-page":"351","volume-title":"Proceedings of the 18th International Conference on Artificial Intelligence and Statistics","volume":"38","author":"Hensman James","year":"2015","unstructured":"James Hensman, Alexander G. Matthews, and Zoubin Ghahramani. 2015. Scalable variational Gaussian process classification. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, Vol. 38. 351\u2013360."},{"key":"e_1_3_3_12_1","volume-title":"Proceedings of the Annual Conference of the Prognostics and Health Management Society","author":"Hoffman Michael","year":"2018","unstructured":"Michael Hoffman, Eunhye Song, Michael Brundage, and Soundar Kumara. 2018. Condition-based maintenance policy optimization using genetic algorithms and Gaussian Markov improvement algorithm. In Proceedings of the Annual Conference of the Prognostics and Health Management Society."},{"key":"e_1_3_3_13_1","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1287\/opre.1050.0237","article-title":"Discrete optimization via simulation using COMPASS","volume":"54","author":"Hong L. Jeff","year":"2006","unstructured":"L. Jeff Hong and Barry Nelson. 2006. Discrete optimization via simulation using COMPASS. Operations Research 54 (2006), 115\u2013129.","journal-title":"Operations Research"},{"issue":"4","key":"e_1_3_3_14_1","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1023\/A:1008306431147","article-title":"Efficient global optimization of expensive black-box functions","volume":"13","author":"Jones Donald R.","year":"1998","unstructured":"Donald R. Jones, Matthias Schonlau, and William J. Welch. 1998. Efficient global optimization of expensive black-box functions. Journal of Global Optimization 13, 4 (1998), 455\u2013492.","journal-title":"Journal of Global Optimization"},{"key":"e_1_3_3_15_1","first-page":"295","volume-title":"International Conference on Machine Learning","author":"Kandasamy Kirthevasan","year":"2015","unstructured":"Kirthevasan Kandasamy, Jeff Schneider, and Barnab\u00e1s P\u00f3czos. 2015. High dimensional Bayesian optimisation and bandits via additive models. In International Conference on Machine Learning. 295\u2013304."},{"key":"e_1_3_3_16_1","first-page":"1546","volume-title":"Advances in Neural Information Processing Systems","author":"Letham Benjamin","year":"2020","unstructured":"Benjamin Letham, Roberto Calandra, Akshara Rai, and Eytan Bakshy. 2020. Re-examining linear embeddings for high-dimensional Bayesian optimization. In Advances in Neural Information Processing Systems, Vol. 33. 1546\u20131558."},{"key":"e_1_3_3_17_1","first-page":"2887","volume-title":"Proceedings of the 2020 Winter Simulation Conference","author":"Li Xinru","year":"2020","unstructured":"Xinru Li and Eunhye Song. 2020. Smart linear algebraic operations for efficient Gaussian Markov improvement algorithm. In Proceedings of the 2020 Winter Simulation Conference. 2887\u20132898."},{"key":"e_1_3_3_18_1","first-page":"3267","volume-title":"Proceedings of the 35th International Conference on Machine Learning","volume":"80","author":"Lu Xiaoyu","year":"2018","unstructured":"Xiaoyu Lu, Javier Gonzalez, Zhenwen Dai, and Neil Lawrence. 2018. Structured variationally auto-encoded optimization. In Proceedings of the 35th International Conference on Machine Learning, Vol. 80. 3267\u20133275."},{"key":"e_1_3_3_19_1","doi-asserted-by":"crossref","first-page":"3528","DOI":"10.1109\/WSC40007.2019.9004851","volume-title":"Proceedings of the 2019 Winter Simulation Conference","author":"Mathesen Logan","year":"2019","unstructured":"Logan Mathesen, Kaushik Keezhnagar Chandrasekar, Xinsheng Li, Giulia Pedrielli, and K. Sel\u00e7uk Candan. 2019. Subspace communication driven search for high dimensional optimization. In Proceedings of the 2019 Winter Simulation Conference. 3528\u20133539."},{"issue":"90","key":"e_1_3_3_20_1","first-page":"2931","article-title":"Hierarchical knowledge gradient for sequential sampling","volume":"12","author":"Mes Martijn R. K.","year":"2011","unstructured":"Martijn R. K. Mes, Warren B. Powell, and Peter I. Frazier. 2011. Hierarchical knowledge gradient for sequential sampling. Journal of Machine Learning Research 12, 90 (2011), 2931\u20132974.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_3_21_1","doi-asserted-by":"crossref","first-page":"1925","DOI":"10.1007\/s10994-020-05899-z","article-title":"High-dimensional Bayesian optimization using low-dimensional feature spaces","volume":"109","author":"Moriconi Riccardo","year":"2020","unstructured":"Riccardo Moriconi, Marc P. Deisenroth, and K. S. Sesh Kumar. 2020. High-dimensional Bayesian optimization using low-dimensional feature spaces. Machine Learning 109 (2020), 1925\u20131943.","journal-title":"Machine Learning"},{"key":"e_1_3_3_22_1","first-page":"9005","volume-title":"Advances in Neural Information Processing Systems 31","author":"Mutny Mojmir","year":"2018","unstructured":"Mojmir Mutny and Andreas Krause. 2018. Efficient high dimensional Bayesian optimization with additivity and quadrature Fourier features. In Advances in Neural Information Processing Systems 31. 9005\u20139016."},{"key":"e_1_3_3_23_1","volume-title":"Proceedings of 33rd Conference on Neural Information Processing Systems","author":"Oh Changyong","year":"2019","unstructured":"Changyong Oh, Jakub M. Tomczak, Efstratios Gavves, and Max Welling. 2019. Combinatorial Bayesian optimization using the graph Cartesian product. In Proceedings of 33rd Conference on Neural Information Processing Systems."},{"key":"e_1_3_3_24_1","first-page":"298","volume-title":"International Conference on Artificial Intelligence and Statistics","author":"Rolland Paul","year":"2018","unstructured":"Paul Rolland, Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. 2018. High-dimensional Bayesian optimization via additive models with overlapping groups. In International Conference on Artificial Intelligence and Statistics. 298\u2013307."},{"issue":"2","key":"e_1_3_3_25_1","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1137\/18M1209386","article-title":"Group kernels for Gaussian process metamodels with categorical inputs","volume":"8","author":"Roustant Olivier","year":"2020","unstructured":"Olivier Roustant, Esp\u00e9ran Padonou, Yves Deville, Alo\u00efs Cl\u00e9ment, Guillaume Perrin, Jean Giorla, and Henry Wynn. 2020. Group kernels for Gaussian process metamodels with categorical inputs. SIAM\/ASA Journal on Uncertainty Quantification 8, 2 (2020), 775\u2013806.","journal-title":"SIAM\/ASA Journal on Uncertainty Quantification"},{"key":"e_1_3_3_26_1","volume-title":"Gaussian Markov Random Fields: Theory and Applications","author":"Rue Havard","year":"2005","unstructured":"Havard Rue and Leonhard Held. 2005. Gaussian Markov Random Fields: Theory and Applications. New York: Chapman and Hall\/CRC."},{"issue":"1","key":"e_1_3_3_27_1","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.2018.1778","article-title":"Gaussian Markov random fields for discrete optimization via simulation: Framework and algorithms","volume":"67","author":"Salemi Peter","year":"2019","unstructured":"Peter Salemi, Eunhye Song, Barry L. Nelson, and Jeremy Staum. 2019. Gaussian Markov random fields for discrete optimization via simulation: Framework and algorithms. Operations Research 67, 1 (2019), 250\u2013266.","journal-title":"Operations Research"},{"issue":"3","key":"e_1_3_3_28_1","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1287\/ijoc.2020.0971","article-title":"Rapid discrete optimization via simulation with Gaussian Markov random fields","volume":"33","author":"Semelhago Mark","year":"2021","unstructured":"Mark Semelhago, Barry L. Nelson, Eunhye Song, and Andreas W\u00e4chter. 2021. Rapid discrete optimization via simulation with Gaussian Markov random fields. INFORMS Journal on Computing 33, 3 (2021), 915\u2013930.","journal-title":"INFORMS Journal on Computing"},{"key":"e_1_3_3_29_1","doi-asserted-by":"crossref","first-page":"2080","DOI":"10.1109\/WSC.2017.8247941","volume-title":"Proceedings of 2017 Winter Simulation Conference","author":"Semelhago Mark","year":"2017","unstructured":"Mark Semelhago, Barry L. Nelson, Andreas W\u00e4chter, and Eunhye Song. 2017. Computational methods for optimization via simulation using Gaussian Markov random fields. In Proceedings of 2017 Winter Simulation Conference. 2080\u20132091."},{"key":"e_1_3_3_30_1","doi-asserted-by":"crossref","first-page":"1790","DOI":"10.1109\/WSC.2018.8632275","volume-title":"Proceedings of 2018 Winter Simulation Conference","author":"Song Eunhye","year":"2018","unstructured":"Eunhye Song and Yi Dong. 2018. Generalized method of moments approach to hyperparameter estimation for Gaussian Markov random fields. In Proceedings of 2018 Winter Simulation Conference. 1790\u20131801."},{"issue":"6","key":"e_1_3_3_31_1","doi-asserted-by":"crossref","first-page":"1416","DOI":"10.1287\/opre.2014.1315","article-title":"Balancing exploitation and exploration in discrete optimization via simulation through a Gaussian process-based search","volume":"62","author":"Sun Lihua","year":"2014","unstructured":"Lihua Sun, L. Jeff Hong, and Zhaolin Hu. 2014. Balancing exploitation and exploration in discrete optimization via simulation through a Gaussian process-based search. Operations Research 62, 6 (2014), 1416\u20131438.","journal-title":"Operations Research"},{"issue":"6","key":"e_1_3_3_32_1","first-page":"2769","article-title":"Measuring and testing dependence by correlation of distances","volume":"35","author":"Sz\u00e9kely G\u00e1bor J.","year":"2007","unstructured":"G\u00e1bor J. Sz\u00e9kely, Maria L. Rizzo, and Nail K. Bakirov. 2007. Measuring and testing dependence by correlation of distances. The Annals of Statistics 35, 6 (2007), 2769\u20132794.","journal-title":"The Annals of Statistics"},{"issue":"2","key":"e_1_3_3_33_1","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1115\/1.1561044","article-title":"Adaptive response surface method using inherited Latin hypercube design points","volume":"125","author":"Wang G. Gary","year":"2003","unstructured":"G. Gary Wang. 2003. Adaptive response surface method using inherited Latin hypercube design points. J. Mech. Des. 125, 2 (2003), 210\u2013220.","journal-title":"J. Mech. Des."},{"key":"e_1_3_3_34_1","first-page":"745","volume-title":"International Conference on Artificial Intelligence and Statistics","author":"Wang Zi","year":"2018","unstructured":"Zi Wang, Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka. 2018. Batched large-scale Bayesian optimization in high-dimensional spaces. In International Conference on Artificial Intelligence and Statistics. 745\u2013754."},{"key":"e_1_3_3_35_1","first-page":"3656","volume-title":"Proceedings of the 34th International Conference on Machine Learning","volume":"70","author":"Wang Zi","year":"2017","unstructured":"Zi Wang, Chengtao Li, Stefanie Jegelka, and Pushmeet Kohli. 2017. Batched high-dimensional Bayesian optimization via structural kernel learning. In Proceedings of the 34th International Conference on Machine Learning, Vol. 70. 3656\u20133664."},{"key":"e_1_3_3_36_1","first-page":"1778","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence","author":"Wang Ziyu","year":"2013","unstructured":"Ziyu Wang, Masrour Zoghi, Frank Hutter, David Matheson, and Nando De Freitas. 2013. Bayesian optimization in high dimensions via random embeddings. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 1778\u20131784."},{"key":"e_1_3_3_37_1","first-page":"361","volume-title":"Journal of Artificial Intelligence Research","author":"Wang Ziyu","year":"2016","unstructured":"Ziyu Wang, Masrour Zoghi, Frank Hutter, David Matheson, and Nando de Freitas. 2016. Bayesian optimization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research, Vol. 55. 361\u2013387."},{"issue":"2","key":"e_1_3_3_38_1","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1287\/opre.2016.1480","article-title":"Bayesian optimization via simulation with pairwise sampling and correlated prior beliefs","volume":"64","author":"Xie Jing","year":"2016","unstructured":"Jing Xie, Peter I. Frazier, and Stephen E. Chick. 2016. Bayesian optimization via simulation with pairwise sampling and correlated prior beliefs. Operations Research 64, 2 (2016), 542\u2013559.","journal-title":"Operations Research"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649463","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:17Z","timestamp":1750291397000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649463"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,16]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3649463"],"URL":"https:\/\/doi.org\/10.1145\/3649463","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,16]]},"assertion":[{"value":"2022-08-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}