电子学报 ›› 2019, Vol. 47 ›› Issue (2): 382-389.DOI: 10.3969/j.issn.0372-2112.2019.02.018

• 学术论文 • 上一篇    下一篇

基于CPU-GPU协同并行内点算法求解结构化非线性规划

杨林峰1,3, 胡桂莉1,2, 张晨1, 张振荣3   

  1. 1. 广西大学计算机与电子信息学院, 广西南宁 530004;
    2. 广西电网有限责任公司贵港供电局, 广西贵港 537100;
    3. 广西多媒体通信与网络技术重点实验室, 广西南宁 530004
  • 收稿日期:2017-08-28 修回日期:2018-09-04 出版日期:2019-02-25
    • 通讯作者:
    • 杨林峰
    • 作者简介:
    • 胡桂莉 女,1990年8月生于广西贵港市,广西大学计算机与电子信息学院硕士研究生,主要研究方向为计算机网络与并行分布式计算.E-mail:794453997@qq.com
    • 基金资助:
    • 国家自然科学基金 (No.51767003,No.51407037,No.61661004); 广西自然科学基金 (No.2016GXNSFDA380019); 广西电力系统最优化与节能技术重点实验室基金 (No.15-A-01-11)

CPU-GPU Cooperative Parallel Interior Point Method for Structured Nonlinear Programming

YANG Lin-feng1,3, HU Gui-li1,2, ZHANG Chen1, ZHANG Zhen-rong3   

  1. 1. School of Computer, Electronics and Information, Guangxi University, Nanning, Guangxi 530004, China;
    2. Guigang Power Supply Bureau, Guangxi Power Grid, Guigang, Guangxi 537100, China;
    3. Guangxi Key Laboratory of Multimedia Communications and Network Technology, Nanning, Guangxi 530004, China
  • Received:2017-08-28 Revised:2018-09-04 Online:2019-02-25 Published:2019-02-25
    • Supported by:
    • National Natural Science Foundation of China (No.51767003, No.51407037, No.61661004); Natural Science Foundation of Guangxi Zhuang Autonomous Region,  China (No.2016GXNSFDA380019); Fund of Guangxi Key Laboratory of Power System Optimization and Energy Technology (No.15-A-01-11)

摘要: 大量工程应用问题可建模为结构化非线性规划,且这类问题的系数矩阵可分为稀疏型和稠密型两种类型.利用原始-对偶内点法(primal dual interior point method,PD-IPM),并结合分布式并行技术可高效求解此类问题.经典工程问题-机组组合(unit commitment,UC)为稀疏系数矩阵的结构化非线性规划,本文根据PD-IPM原理,对UC模型进行连续松弛预处理,结合快速解耦技术解耦牛顿修正方程并设计CPU-GPU协同并行算法求解子问题,最后将结果与带稠密型子问题的结构化非线性规划的求解结果进行比较和分析.实验结果显示,本文所设计的算法对于两种不同类型的结构化非线性规划求解均能获得较好的加速比.

关键词: 非线性规划, 内点法, 机组组合, CPU-GPU协同, 并行计算

Abstract: A lot of practical application problems can be modeled as structured nonlinearprogramming,and these problems always have two type of coefficients matrices:sparse and dense.Combining the principle of primal dual interior point method(PD-IPM) and the distributed parallel technology can solve the problem efficiently.The unit commitment(UC)is a classical engineering problem which can be formulated as a structured nonlinear programming with sparse coefficients matrices.In this paper,according to the PD-IPM principle,the UC model is continuous relaxation preprocessed,and the Newton correction equations are decoupled by using the fast decoupling technique,which can be used to obtain the independent sub problems.Then,a CPU-GPU collaborative parallel method is proposed to solve the sub problems in parallel and the results are compared with the results of structured nonlinear programming with dense sub problem.The experimental results show that the proposed method for solving two different types of structured nonlinear programming has achieved a certain speedup.

Key words: nonlinear programming, interior point method, unit commitment, CPU-GPU cooperative, parallel computing

中图分类号: