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

Ting L. Lei, Rongrong Wang, Zhen LeiIsprs Int. J. geo inf 2025 · DOI

TL;DR

This paper introduces a novel approach to solving large-scale spatial optimization problems by leveraging the power of modern deep learning frameworks and GPGPU acceleration. By adapting Lagrangian Relaxation (LR) algorithms within a deep learning paradigm, the authors achieve significant speedups and enable the solution of previously intractable problem sizes, making fine-grained spatial analysis more feasible.

What Problem Does This Paper Address?

Spatial optimization problems, common in Geographic Information Systems (GIS), involve making optimal location decisions for facilities, services, and resources. A classic example is the p-median problem, which aims to find the best locations for a fixed number of facilities to minimize service distances to customers. While Lagrangian Relaxation (LR) is a powerful technique for solving these NP-hard problems, its practical adoption has been limited due to:

  • High development cost: Creating specialized LR algorithms for each problem is complex and time-consuming, requiring manual derivation of gradients and implementation of optimization routines.
  • Computational expense: Solving large instances of these problems can be computationally intensive, even with efficient LR algorithms.
  • Difficulty in parallelization: Effectively utilizing parallel computing resources like GPGPUs for LR has been a long-standing challenge.

This paper aims to overcome these hurdles by integrating LR with deep learning frameworks, which offer mature tools for gradient computation, optimization, and GPGPU acceleration.

Methods

The core innovation lies in adapting the deep learning (DL) workflow for Lagrangian Relaxation. Instead of training a neural network, the DL framework's components are repurposed:

  • Dataset Module: Loads spatial optimization problem data (e.g., distance matrices, population data).
  • Training Step: Computes both the primal and dual objectives of the LR problem. The dual objective is used for gradient descent, while the difference between primal and dual (optimality gap) serves as a termination criterion.
  • Optimizer: Leverages the vast array of pre-built optimizers (e.g., Adam, SGD) available in DL libraries, eliminating the need to implement gradient descent from scratch.
  • GPGPU Acceleration: The DL framework automatically utilizes GPGPU for massive parallelization of computations, significantly speeding up the optimization process.
  • Automatic Differentiation: DL frameworks automatically compute gradients, removing the need for manual derivation of complex mathematical expressions.

The authors specifically adapt this framework for the p-median problem by relaxing assignment constraints and formulating a dual problem that is amenable to gradient optimization.

Datasets

The study uses the Swain 55-node dataset as a base for testing. To evaluate the scalability of their approach, they generated larger datasets by densifying the original Swain dataset. These larger datasets, referred to as Swain55_big50, Swain55_big100, Swain55_big200, and Swain55_big300, represent problem instances with up to 16,500 nodes, significantly larger than typical p-median datasets solved by optimal algorithms.

Key Insights and Ideas

  • DL Frameworks as General Optimization Tools: The paper demonstrates that the core components of deep learning frameworks (optimizers, autograd, GPGPU support) are highly adaptable for solving general optimization problems beyond neural networks.
  • Bridging the Gap in LR Development: By using DL libraries, the authors drastically reduce the development effort for LR algorithms, allowing researchers to focus on defining the problem's dual objective rather than implementing complex optimization machinery.
  • GPGPU for LR is Feasible and Effective: The research validates that GPGPU can be effectively harnessed for LR, leading to substantial speedups and enabling the solution of much larger problem instances than previously possible.
  • Optimality Gap as a Reliable Termination Criterion: Unlike standard DL, where convergence is often heuristic, the LR framework's optimality gap provides a mathematically sound criterion for determining when an optimal or near-optimal solution has been reached.

Key Results

  • Massive Speedups: The GPU-based LR algorithm achieved speedups of approximately 104x compared to the OPL solver and 12.5x compared to the CPU version of their LR algorithm.
  • Scalability: The algorithm successfully solved large p-median problem instances with over 15,000 nodes, which were previously intractable for optimal solvers.
  • High GPU Utilization: The GPU utilization rate on an NVIDIA RTX 4090 reached approximately 90%, indicating efficient use of hardware resources.
  • Correctness: The algorithm produced results consistent with known optimal solutions for smaller datasets, and the convergence curves showed the expected behavior of primal and dual objectives.
  • Optimizer Performance: While various optimizers were tested, the Adam family (specifically Adamax) showed strong performance, with a U-shaped convergence curve for learning rates.

Limitations and Future Work

  • Dataset Size Limitation: The current dataset sizes are limited by GPU memory. The authors suggest exploring more efficient data representations (e.g., sparse matrices) or investigating mini-batching techniques for LR.
  • Parameter Tuning: The current method uses a basic grid search for learning rates, which is time-consuming. Future work could involve adapting DL parameter tuning tools.
  • Optimizer Interchangeability: While optimizers can be used interchangeably, their performance varies. Further investigation into why certain optimizers perform better and how to adapt them for LR is suggested.
  • Transferability of Parameters: Unlike DL, the learned parameters (Lagrangian multipliers) are not directly transferable to new datasets, limiting their use in a "prediction" stage.
  • Integration with GIS: The authors envision integrating this GPU-enabled LR approach into GIS systems for real-time or near-real-time spatial optimization.

Summary updated

BibTeX
@article{lei2025massively,
  author = {Ting L. Lei and Rongrong Wang and Zhen Lei},
  title = {{Massively Parallel Lagrangian Relaxation Algorithm for Solving Large-Scale Spatial Optimization Problems Using GPGPU}},
  journal = {Isprs Int. J. geo inf},
  year = {2025},
  doi = {10.3390/ijgi14110419},
}
Figure