化工学报 ›› 2012, Vol. 63 ›› Issue (11): 3597-3601.DOI: 10.3969/j.issn.0438-1157.2012.11.032

• 过程系统工程 • 上一篇    下一篇

基于GPU加速求解MINLP问题的SQP并行算法

康丽霞1, 张燕蓉2, 唐亚哲2, 刘永忠1,3   

  1. 1. 西安交通大学化学工程系, 陕西 西安 710049;
    2. 西安交通大学计算机科学与技术系, 陕西 西安 710049;
    3. 热流科学与工程教育部重点实验室, 陕西 西安 710049
  • 收稿日期:2012-08-04 修回日期:2012-08-12 出版日期:2012-11-05 发布日期:2012-11-05
  • 通讯作者: 刘永忠
  • 作者简介:康丽霞(1989-),女,博士研究生。
  • 基金资助:

    陕西省自然科学基金项目(2012JM2001);国家自然科学基金重点项目(20936004);中央高校基本科研业务费专项资金资助项目。

Paralleled SQP algorithm for solution of MINLP problems based on GPU acceleration

KANG Lixia1, ZHANG Yanrong2, TANG Yazhe2, LIU Yongzhong1,3   

  1. 1. Department of Chemical Engineering, Xi’an Jiaotong University, Xi’an 710049, Shaanxi, China;
    2. Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, Shaanxi, China;
    3. Key Laboratory of Thermo-Fluid Science and Engineering, Ministry of Education, Xi’an 710049, Shaanxi, China
  • Received:2012-08-04 Revised:2012-08-12 Online:2012-11-05 Published:2012-11-05
  • Supported by:

    supported by the Natural Science Foundation of Shaanxi Province(2012JM2001),the National Natural Science Foundation of China(20936004)and the Fundamental Research Funds for the Central University.

摘要: 针对确定性算法求解大型复杂混合整数非线性规划的时间不可接受问题,通过对序贯二次规划算法(SQP)和图形处理器(GPU)的架构特点分析,提出了基于GPU加速策略的并行化SQP算法。算法的主要思想是通过枚举法确定二元变量的取值,在保证取值完整的基础上,使用CPU+GPU的并行策略,同时运用大量线程进行非线性规划子问题的求解。算例的数值实验结果表明:本文所提出的算法较之传统串行计算具有较好的加速效果,特别适合求解二元变量较多,约束条件相对少的MINLP问题。

关键词: 混合整数非线性规划, GPU, 序贯二次规划法, 加速

Abstract: To solve the problem of unacceptable execution time for solving large-scale and complex mixed integer non-linear programming problems by using deterministic algorithms,a paralleled sequential quadratic programming algorithm on the basis of GPU acceleration was proposed,in which a thorough analysis of the SQP algorithm and the framework of GPU was made.In the proposed method,enumeration algorithm was used to deal with binary variables,and the CPU +GPU strategy and the GPU in parallel were used to accelerate convergence rate.Numerical experiments show that compared to the typical serial algorithm,the proposed algorithm possesses a better convergence performance for solving MINLP problems with more binary variables and less constraints.

Key words: MINLP, GPU, sequential quadratic programming, acceleration

中图分类号: