Gpu algorithm speeds up mixed integer optimization primal heuristics
PaNGEA: Parallel Node Generation and Exploration Algorithm on GPU
Distributed, Parallel, and Cluster Computing
Summary
Finding good solutions quickly in mixed-integer optimization problems is very important but can be slow. The authors created a new algorithm called PaNGEA that runs well on GPUs by solving many smaller problems in parallel and using local search techniques. Their experiments show that doing this on a GPU gives better results faster than traditional CPU methods, both when solving single problems and multiple problems at the same time. This approach helps optimization software get good solutions more efficiently.
What this means in practice
- •For optimization software developers: Improve primal heuristics in mixed-integer optimization solvers by integrating GPU-accelerated parallel node exploration to speed up solution quality improvement.
- •For operations management teams: Obtain high-quality feasible solutions faster for complex scheduling and planning problems using GPU-based parallel optimization heuristics.
Authors
Jean Pauphilet, Yupeng Wu
Abstract
Primal heuristics for finding high-quality feasible solutions are an important component in mixed-integer optimization (MIO) solvers. Recent advances in GPU-accelerated optimization algorithms show the potential of GPU acceleration for continuous optimization. In this paper, we introduce the Parallel Node Generation and Exploration Algorithm (PaNGEA), a GPU-friendly MIO primal heuristic. PaNGEA explores restricted subproblems by combining linear-relaxation solves with a local-search procedure designed for efficient batched execution on GPUs. In addition, instead of relying on a single heuristic for iterative variable fixing, we leverage GPU batching capabilities to generate and explore multiple subproblems in parallel. PaNGEA leverages GPU capabilities in two ways. First, on 283 MIPcc26 and MIPLIB instances, implementing a single-node primal heuristic on the GPU reduces the average gap integral by 8-18% relative to its CPU counterpart. Second, generating and exploring multiple nodes in parallel further reduces the average gap integral by 12-19%.