N2N: A Parallel Framework for Large-Scale MILP under Distributed Memory
Parallelization has emerged as a promising approach for accelerating MILP solving. However, the complexity of the branch-and-bound (B&B) framework and the numerous effective algorithm components in MILP solvers make it difficult to parallelize. In this study, a scalable parallel framework, N2N (a node-to-node framework that maps the B&B nodes to distributed computing nodes), was proposed to solve large-scale problems in a distributed memory computing environment. Both deterministic and nondeterministic modes are supported, and the framework is designed to be easily integrated with existing solvers. Regarding the deterministic mode, a novel sliding-window-based algorithm was designed and implemented to ensure that tasks are generated and solved in a deterministic order. Moreover, several advanced techniques, such as the utilization of CP search and general primal heuristics, have been developed to fully utilize distributed computing resources and capabilities of base solvers. Adaptive solving and data communication optimization were also investigated. A popular open-source MILP solver, SCIP, was integrated into N2N as the base solver, yielding N2N-SCIP. Extensive computational experiments were conducted to evaluate the performance of N2N-SCIP compared to ParaSCIP, which is a state-of-the-art distributed parallel MILP solver under the UG framework. The nondeterministic N2N-SCIP achieves speedups of 22.52 and 12.71 with 1,000 MPI processes on the Kunpeng and x86 computing clusters, which is 1.98 and 2.08 times faster than ParaSCIP, respectively. In the deterministic mode, N2N-SCIP also shows significant performance improvements over ParaSCIP across different process numbers and computing clusters. To validate the generality of N2N, HiGHS, another open-source solver, was integrated into N2N. The related results are analyzed, and the requirements of N2N on base solvers are also concluded.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Parallel Domain-Decomposition Algorithms for Complexity Certification of Branch-and-Bound Algorithms for Mixed-Integer Linear and Quadratic Programming
When implementing model predictive control (MPC) for hybrid systems with a linear or a quadratic performance measure, a mixed-integer linear program (MILP) or a mixed-integer quadratic program (MIQP) needs to be solved, …
Model Predictive ControlScalable Joint Resource Allocation for SLO-Constrained LLM Inference in Heterogeneous GPU Clouds
Serving large language model (LLM) inference in cloud environments requires jointly optimizing model selection, GPU provisioning, parallelism configuration, and workload routing under latency, accuracy, memory, and budge…
Learning from Images: Proactive Caching with Parallel Convolutional Neural Networks
With the continuous trend of data explosion, delivering packets from data servers to end users causes increased stress on both the fronthaul and backhaul traffic of mobile networks. To mitigate this problem, caching popu…
Decision MakingEnhancing Scalability of Optimal Kron-based Reduction of Networks (Opti-KRON) via Decomposition with Community Detection
Electrical networks contain thousands of interconnected nodes and edges, which leads to computational challenges in some power system studies. To address these challenges, we contend that network reductions can serve as …
Community DetectionCollab-Solver: Collaborative Solving Policy Learning for Mixed-Integer Linear Programming
Mixed-integer linear programming (MILP) has been a fundamental problem in combinatorial optimization. Conventional MILP solving mainly relies on carefully designed heuristics embedded in the branch-and-bound framework. D…