Alibaba's Damo Academy releases GPU version solver for the first time, breaking the "unsolvable" challenge of solving problems with billions of variables.

On May 28th, Alibaba's (09988) DAMO Academy released the GPU version of their "MindOpt" solver, which fully utilizes the parallel acceleration features of GPU and introduces new algorithms to overcome the "long tail effect" challenge. Testing on around 2000 common cases shows that MindOpt can stably solve over 99% of the problem types to high precision and even support linear programming problems with billions of variables, which were traditionally considered "unsolvable". The solver, known as the "heart of industrial software", is responsible for complex calculations in key areas such as power dispatching, flight scheduling, advanced manufacturing, and financial management. Traditional linear programming solvers are designed based on CPUs and rely on complex matrix decomposition calculations. As the problem scale increases, the memory requirements exponentially grow, and the limited parallelism of traditional solving algorithms leads to convergence issues, sometimes even causing crashes. In recent years, the industry has been actively exploring GPU solvers, shifting the core calculations from matrix decomposition to sparse matrix-vector multiplication. This fully utilizes the high concurrency and bandwidth capabilities of GPUs and avoids memory expansion issues. However, this approach often faces the "long tail effect" during convergence, where precision improvement slows down towards the later stages and fails to meet the final accuracy requirements, severely limiting the practicality of GPU solvers. To address this, the DAMO Academy developed the MindOpt solver GPU version, introducing advanced algorithm acceleration strategies and deeply optimizing GPU kernel computation. By combining mathematical programming techniques with GPU engineering advantages, the solver effectively mitigates the aforementioned "long tail effect," bridging the gap from "being able to calculate" to "accurate calculation." It can stably converge to the required precision in business-critical large-scale problems. The team conducted detailed tests on the GPU version of the MindOpt solver on over 2000 common linear programming cases, covering various problem types and precision requirements. The results showed that the solver's coverage and solving performance reached industry-leading levels. For high-precision requirements, MindOpt solver's GPU version can stably solve over 99% of problem types, surpassing the 96.7% to 98.3% performance of mainstream GPU solvers in the same test set. Particularly in solving large-scale problems, the success rate of the MindOpt solver was improved by over 14% compared to mainstream products in the industry, with an average speed increase of 2.67 times. When facing traditionally unsolvable large-scale problems with billions of variables, the GPU version of the MindOpt solver can stably solve over 80% of common problem types, filling in critical gaps. This product has outstanding application value in various industries such as internet, finance, logistics, power, and integrated circuits. For instance, a large digital advertising platform needs to allocate traffic to hundreds of millions of users, involving around 330 million variables and 16 million constraints each time, with the requirement to complete it within 2 hours. Most commercial solvers failed to provide a feasible solution even after 48 hours of running, or even crashed, while the MindOpt solver GPU version achieved reliable accuracy in just 1700 seconds. Yan Wotao, the head of the Decision Intelligence Laboratory at DAMO Academy and an internationally renowned applied mathematician, stated: "The scale of computations in various industries is growing exponentially, leading to more and more billion-variable problems that traditional solvers struggle to handle. We will continue to unlock more potentials of new hardware in the field of operations research and optimization, driving solvers into the era of GPU acceleration."