A mixed-integer quadratic programming solver based on GPU

摘要

Solving the mixed-integer quadratic programming (MIQP) problem is often required in many practical applications. But the existing solvers always encounter the contradiction between high precision and low time consumption. To solve this problem, this paper designs a new MIQP solver by developing a parallel branch-and-bound algorithm utilizing multi-point radiation based on the multithreading parallel structure of GPU. This solver can obtain the global optimal solution by inheriting the advantages of the classical branch-and-bound algorithm. To increase the efficiency of the MIQP solver, for the quadratic programming (QP) to be solved each time during iteration, we fully use the massive parallelism of GPU and adopt the discrete-time simplified dual neural network. The idea of multi-point radiation is used to simultaneously generate multiple search branches to improve the search efficiency. These strategies enhance the throughput and the degree of parallelization. The high computational efficiency of the proposed MIQP solver is verified by test results with solving time statistics for multiple examples.