Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation
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 so...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | ISPRS International Journal of Geo-Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2220-9964/14/1/15 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832588343015112704 |
|---|---|
| author | Zhen Lei Ting L. Lei |
| author_facet | Zhen Lei Ting L. Lei |
| author_sort | Zhen Lei |
| collection | DOAJ |
| description | 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 <i>p</i>-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 <i>p</i>-median. And such automation can be applied to numerous other optimization problems. |
| format | Article |
| id | doaj-art-5617c7c3344243398585db8807e61529 |
| institution | Kabale University |
| issn | 2220-9964 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | ISPRS International Journal of Geo-Information |
| spelling | doaj-art-5617c7c3344243398585db8807e615292025-01-24T13:34:59ZengMDPI AGISPRS International Journal of Geo-Information2220-99642025-01-011411510.3390/ijgi14010015Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient ComputationZhen Lei0Ting L. Lei1College of Automation, Wuhan University of Technology, Wuhan 430070, ChinaDepartment of Geography & Atmospheric Science, University of Kansas, Lawrence, KS 66045, USASpatial 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 <i>p</i>-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 <i>p</i>-median. And such automation can be applied to numerous other optimization problems.https://www.mdpi.com/2220-9964/14/1/15GISdiscrete optimizationLagrangian relaxationalgorithmgradient descent |
| spellingShingle | Zhen Lei Ting L. Lei Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation ISPRS International Journal of Geo-Information GIS discrete optimization Lagrangian relaxation algorithm gradient descent |
| title | Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation |
| title_full | Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation |
| title_fullStr | Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation |
| title_full_unstemmed | Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation |
| title_short | Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation |
| title_sort | solving spatial optimization problems via lagrangian relaxation and automatic gradient computation |
| topic | GIS discrete optimization Lagrangian relaxation algorithm gradient descent |
| url | https://www.mdpi.com/2220-9964/14/1/15 |
| work_keys_str_mv | AT zhenlei solvingspatialoptimizationproblemsvialagrangianrelaxationandautomaticgradientcomputation AT tingllei solvingspatialoptimizationproblemsvialagrangianrelaxationandautomaticgradientcomputation |