Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation

doi:10.3390/ijgi14010015

Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation

2025-01-02

0

OA

AI

DOI：10.3390/ijgi14010015

原文链接

原文求助

摘要

En 中文

空间优化是GIS和空间分析的有机组成部分。它涉及在空间中做出各种决策，范围从公共设施的选址到车辆路径规划和政治选区划分。尽管这类问题（尤其是大型实例）有用，但通常难以使用通用数学规划解决（因其通用性）。传统上，替代的解决方案是拉格朗日松弛法，如果设计得当，该方法可以快速且最优。需要推导拉格朗日对偶问题及其（子）梯度，并通过梯度下降等搜索过程逼近最优解。尽管具有优点，但拉格朗日松弛作为一种求解算法，要求手动推导（子）梯度，这不仅容易出错，还使得求解算法难以开发且高度依赖具体模型。本文旨在通过采用现代深度学习中原有的自动（子）梯度（autograd）计算能力，为GIS从业者简化拉格朗日松弛算法的开发。以经典的p-中位数问题为例，我们展示了如何使用纸笔开发拉格朗日松弛，以及如何利用autograd实现（子）梯度计算的自动化。因此，人类专家只需在科学计算语言（如Python）中实现拉格朗日问题，系统即可找到该代码的（子）梯度，即使其中包含复杂循环和条件语句。我们验证了基于autograd的算法版本与基于手动推导梯度的原始版本等价。通过自动化（子）梯度计算，我们显著降低了为p-中位数开发拉格朗日算法的成本。此类自动化还可应用于众多其他优化问题。

Keyword:

GIS

discrete optimization

Lagrangian relaxation

algorithm

gradient descent

Solving Spatial Optimization Problems via Lagrangian Relaxation and Automatic Gradient Computation

摘要

期刊

机构

引用论文