Massively Parallel Lagrangian Relaxation Algorithm for Solving Large-Scale Spatial Optimization Problems Using GPGPU

Ting Lei

doi:10.3390/ijgi14110419

2025-10-26

Ting Lei

Rongrong Wang

Zhen Lei *

DOI：10.3390/ijgi14110419

原文链接

查看原文

摘要

En 中文

拉格朗日松弛（LR）是解决地理空间分析和GIS中空间优化问题的有效方法。其中，它已被用于解决自1990年代以来作为GIS中统一局部模型的经典p-中位问题。尽管其效率较高，但LR算法在实践中的应用有限，不如OPL/CPLEX或GPLK等现成求解器那样广泛使用。这主要是因为开发成本高昂，包括：（i）为每个优化模型开发完整的梯度下降算法的成本，以及为提高速度而采用的各种技巧和修改；（ii）对于大规模问题实例，计算成本可能很高；（iii）需要测试并选择不同的松弛方案；（iv）需要在编程语言中推导和计算梯度。本研究旨在通过利用GPGPU的计算能力和现代深度学习（DL）框架（如PyTorch）的现有功能，解决前三个问题。基于对DL与一般优化之间共性与差异的分析，我们调整了DL库以求解LR问题。结果，我们可以从DL库中的众多梯度下降策略（即优化器）中进行选择，而无需从零开始重新设计。实验表明，在DL库中实现LR不仅可行，而且便捷。梯度向量会自动跟踪和计算。此外，GPGPU的计算能力会自动用于并行化优化算法（这是运筹学中长期存在的难题）。针对经典p-中位问题的实验表明，使用基于GPU的LR算法可以最优或近最优地求解规模更大的问题实例（超过15,000个节点）。这种能力使GIS能够进行更精细的分析。与OPL求解器和算法的CPU版本相比，GPU版本分别实现了104倍和12.5倍的速度提升。在RTX 4090 GPU上的GPU利用率达到90%。最后，我们总结了研究结论，并对未来工作进行了展望。

Keyword:

discrete optimization

parallel computing

Lagrangian relaxation

algorithm

GPU