{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T08:07:50Z","timestamp":1761898070404,"version":"build-2065373602"},"reference-count":12,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T00:00:00Z","timestamp":1735776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Natural Science Foundation","award":["BCS-2215155","41971334"],"award-info":[{"award-number":["BCS-2215155","41971334"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China (NSFC)","doi-asserted-by":"publisher","award":["BCS-2215155","41971334"],"award-info":[{"award-number":["BCS-2215155","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>Spatial optimization is an integral part of GIS and spatial analysis. It involves making various decisions in space, ranging from the location of public facilities to vehicle routing and political districting. While useful, such problems (especially large problem instances) are often difficult to solve using general mathematical programming (due to their generality). Traditionally, an alternative solution method is Lagrangian relaxation, which, if well-designed, can be fast and optimal. One has to derive the Lagrangian dual problem and its (sub)gradients, and move towards the optimal solution via a search process such as gradient descent. Despite its merits, Lagrangian relaxation as a solution algorithm requires one to derive the (sub)gradients manually, which is error-prone and makes the solution algorithm difficult to develop and highly dependent on the model at hand. This paper aims to ease the development of Lagrangian relaxation algorithms for GIS practitioners by employing the automatic (sub)gradient (autograd) computation capabilities originally developed in modern Deep Learning. Using the classic p-median problem as an example, we demonstrate how Lagrangian relaxation can be developed with paper and pencil, and how the (sub)gradient computation derivation can be automated using autograd. As such, the human expert only needs to implement the Lagrangian problem in a scientific computing language (such as Python), and the system can find the (sub)gradients of this code, even if it contains complex loops and conditional statements. We verify that the autograd version of the algorithm is equivalent to the original version with manually derived gradients. By automating the (sub)gradient computation, we significantly lower the cost of developing a Lagrangian algorithm for the p-median. And such automation can be applied to numerous other optimization problems.<\/jats:p>","DOI":"10.3390\/ijgi14010015","type":"journal-article","created":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T06:05:10Z","timestamp":1735797910000},"page":"15","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1378-4903","authenticated-orcid":false,"given":"Zhen","family":"Lei","sequence":"first","affiliation":[{"name":"College of Automation, Wuhan University of Technology, Wuhan 430070, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2385-9128","authenticated-orcid":false,"given":"Ting L.","family":"Lei","sequence":"additional","affiliation":[{"name":"Department of Geography & Atmospheric Science, University of Kansas, Lawrence, KS 66045, USA"}]}],"member":"1968","published-online":{"date-parts":[[2025,1,2]]},"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":"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_4","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_5","doi-asserted-by":"crossref","unstructured":"Boyd, S.P., and Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"692","DOI":"10.1287\/mnsc.16.11.692","article-title":"An analysis of private and public sector location models","volume":"16","author":"ReVelle","year":"1970","journal-title":"Manag. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1287\/opre.25.2.338","article-title":"The one-dimensional generalized lagrange multiplier problem","volume":"25","author":"Greenberg","year":"1977","journal-title":"Oper. Res."},{"key":"ref_8","unstructured":"Maclaurin, D., Duvenaud, D., and Johnson, M. (2024, December 10). Autograd 1.6.2. Available online: https:\/\/pypi.org\/project\/autograd\/."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1693","DOI":"10.1111\/tgis.12804","article-title":"Integrating GIS and location modeling: A relational approach","volume":"25","author":"Lei","year":"2021","journal-title":"Trans. GIS"},{"key":"ref_10","unstructured":"Swain, R.W. (1971). A Decomposition Algorithm for a Class of Facility Location Problems. [Ph.D. Thesis, Cornell University]."},{"key":"ref_11","unstructured":"Lei, T.L. (2010). Location Modeling Utilizing Closest and Generalized Closest Transport\/Interaction Assignment Constructs. [Ph.D. Dissertation, University of California]."},{"key":"ref_12","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"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/14\/1\/15\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T15:23:31Z","timestamp":1759850611000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/14\/1\/15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,2]]},"references-count":12,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,1]]}},"alternative-id":["ijgi14010015"],"URL":"https:\/\/doi.org\/10.3390\/ijgi14010015","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2025,1,2]]}}}