一种求解机组组合问题的内点半定规划GPU并行算法

摘要

Because the time consumption is too heavy when the interior point algorithm is used to solve the SDP(SemiDefinite Programming) model of unit commitment,the Krylov subspace parallel algorithm based on GPU(Graphic Processing Unit) is proposed,which,based on the matrix sectioning technology and in CSR storage format,applies the preconditioned QMR(Quasi-Minimal Residual) method to calculate the parallel Incomplete Cholesky preconditioning matrix by GPU.Analysis of the calculations for linear equation sets of different sizes shows that,with better parallel speedup ratio,QMR parallel algorithm is superior to the traditional Cholesky direct method in speed and memory.Simulative results of six systems of 10～100units also show that,an approximate optimal solution can be obtained with less computing time by the SDP parallel interior point method.%针对内点法求解机组组合问题的半定规划(SDP)模型时大规模线性方程组计算时间太长的问题,提出一种基于图形处理器(GPU)的Krylov子空间并行算法.该算法采用预条件处理的拟最小残差法(QMR法),并以矩阵分块技术为基础,在CSR存储格式下使用GPU实现Incomplete Cholesky并行预处理矩阵的计算.通过对不同规模线性方程组的计算分析表明,与传统的Cholesky直接法相比,QMR并行算法具有速度和存储优势,可获得良好的并行加速比.10～100机6个系统的仿真结果也表明,该SDP并行内点法在减少计算时间的同时可求得近似最优解.