{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:25:17Z","timestamp":1761895517363,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T00:00:00Z","timestamp":1761436800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"Natural Science Foundation","doi-asserted-by":"publisher","award":["BCS-2215155"],"award-info":[{"award-number":["BCS-2215155"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["41971334"],"award-info":[{"award-number":["41971334"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Lagrangian Relaxation (LR) is an effective method for solving spatial optimization problems in geospatial analysis and GIS. Among others, it has been used to solve the classic p-median problem that served as a unified local model in GIS since the 1990s. Despite its efficiency, the LR algorithm has seen limited usage in practice and is not as widely used as off-the-shelf solvers such as OPL\/CPLEX or GPLK. This is primarily because of the high cost of development, which includes (i) the cost of developing a full gradient descent algorithm for each optimization model with various tricks and modifications to improve the speed, (ii) the computational cost can be high for large problem instances, (iii) the need to test and choose from different relaxation schemes, and (iv) the need to derive and compute the gradients in a programming language. In this study, we aim to solve the first three issues by utilizing the computational power of GPGPU and existing facilities of modern deep learning (DL) frameworks such as PyTorch. Based on an analysis of the commonalities and differences between DL and general optimization, we adapt DL libraries for solving LR problems. As a result, we can choose from the many gradient descent strategies (known as \u201coptimizers\u201d) in DL libraries rather than reinventing them from scratch. Experiments show that implementing LR in DL libraries is not only feasible but also convenient. Gradient vectors are automatically tracked and computed. Furthermore, the computational power of GPGPU is automatically used to parallelize the optimization algorithm (a long-term difficulty in operations research). Experiments with the classic p-median problem show that we can solve much larger problem instances (of more than 15,000 nodes) optimally or nearly optimally using the GPU-based LR algorithm. Such capabilities allow for a more fine-grained analysis in GIS. Comparisons with the OPL solver and CPU version of the algorithm show that the GPU version achieves speedups of 104 and 12.5, respectively. The GPU utilization rate on an RTX 4090 GPU reaches 90%. We then conclude with a summary of the findings and remarks regarding future work.<\/jats:p>","DOI":"10.3390\/ijgi14110419","type":"journal-article","created":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T02:23:28Z","timestamp":1761704608000},"page":"419","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Massively Parallel Lagrangian Relaxation Algorithm for Solving Large-Scale Spatial Optimization Problems Using GPGPU"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2385-9128","authenticated-orcid":false,"given":"Ting L.","family":"Lei","sequence":"first","affiliation":[{"name":"Department of Geography & Atmospheric Science, University of Kansas, Lawrence, KS 66045, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rongrong","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computational Mathematics, Science, and Engineering (CMSE), Michigan State University, East Lansing, MI 48824, USA"},{"name":"Department of Mathematics, Michigan State University, East Lansing, MI 48824, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1378-4903","authenticated-orcid":false,"given":"Zhen","family":"Lei","sequence":"additional","affiliation":[{"name":"College of Automation, Wuhan University of Technology, Wuhan 430070, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,10,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1287\/opre.12.3.450","article-title":"Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph","volume":"12","author":"Hakimi","year":"1964","journal-title":"Oper. Res."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1287\/opre.13.3.462","article-title":"Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems","volume":"13","author":"Hakimi","year":"1965","journal-title":"Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1287\/trsc.3.4.352","article-title":"Optimal Locations for Centers in a Network","volume":"3","author":"Goldman","year":"1969","journal-title":"Transp. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1287\/opre.20.5.967","article-title":"Optimum Locations of Centers in Networks","volume":"20","author":"Hakimi","year":"1972","journal-title":"Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1068\/a160305","article-title":"The p-Median Structure as a Unified Linear Model for Location-Allocation Analysis","volume":"16","author":"Hillsman","year":"1984","journal-title":"Environ. Plan. A"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1287\/mnsc.11.2.213","article-title":"Plant Location Under Economies-of-Scale-Decentralization and Computation","volume":"11","author":"Manne","year":"1964","journal-title":"Manag. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1111\/j.1435-5597.1974.tb00902.x","article-title":"The Maximal Covering Location Problem","volume":"32","author":"Church","year":"1974","journal-title":"Pap. Reg. Sci. Assoc."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1287\/trsc.20.2.92","article-title":"The Location of Interacting Hub Facilities","volume":"20","year":"1986","journal-title":"Transp. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1080\/13658816.2015.1041959","article-title":"A Unified Approach for Location-Allocation Analysis: Integrating GIS, Distributed Computing and Spatial Optimization","volume":"30","author":"Lei","year":"2016","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.ejor.2005.06.044","article-title":"A Lagrangian Relaxation-Based Heuristic for the Vehicle Routing with Full Container Load","volume":"176","author":"Imai","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"955","DOI":"10.1287\/opre.16.5.955","article-title":"Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph","volume":"16","author":"Teitz","year":"1968","journal-title":"Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.27.1.1","article-title":"The Lagrangian Relaxation Method for Solving Integer Programming Problems","volume":"27","author":"Fisher","year":"1981","journal-title":"Manag. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/0377-2217(85)90012-8","article-title":"A Comparison of Two Dual-Based Procedures for Solving the p-Median Problem","volume":"20","author":"Hanjoul","year":"1985","journal-title":"Eur. J. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Lei, Z., and Lei, T.L. (2025). Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation. ISPRS Int. J. Geo-Inf., 14.","DOI":"10.3390\/ijgi14010015"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1145\/3065386","article-title":"ImageNet Classification with Deep Convolutional Neural Networks","volume":"60","author":"Krizhevsky","year":"2017","journal-title":"Commun. ACM"},{"key":"ref_16","unstructured":"Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, \u0141., and Polosukhin, I. (2017, January 4\u20139). Attention Is All You Need. Proceedings of the 31st Annual Conference on Neural Information Processing Systems (NIPS), LA Jolla, CA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1111\/j.1538-4632.1970.tb00142.x","article-title":"Central Facilities Location","volume":"2","author":"ReVelle","year":"1970","journal-title":"Geogr. Anal."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/BF01580223","article-title":"Validation of Subgradient Optimization","volume":"6","author":"Held","year":"1974","journal-title":"Math. Program."},{"key":"ref_19","unstructured":"Kingma, D.P., and Ba, J. (2015, January 7\u20139). Adam: A Method for Stochastic Optimization. Proceedings of the International Conference on Learning Representations (ICLR), San Diego, CA, USA."},{"key":"ref_20","unstructured":"Swain, R.W. (1971). A Decomposition Algorithm for a Class of Facility Location Problems. [Ph.D. Thesis, Cornell University]."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/14\/11\/419\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T05:52:10Z","timestamp":1761889930000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/14\/11\/419"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,26]]},"references-count":20,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2025,11]]}},"alternative-id":["ijgi14110419"],"URL":"https:\/\/doi.org\/10.3390\/ijgi14110419","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2025,10,26]]}}}