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

doi:10.3969/j.issn.0438-1157.2012.11.032

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

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

康丽霞¹, 张燕蓉², 唐亚哲², 刘永忠^1,3

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 Lixia¹, ZHANG Yanrong², TANG Yazhe², LIU Yongzhong^1,3

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.

摘要/Abstract

摘要： 针对确定性算法求解大型复杂混合整数非线性规划的时间不可接受问题,通过对序贯二次规划算法(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

中图分类号:

TQ021.8

康丽霞, 张燕蓉, 唐亚哲, 刘永忠. 基于GPU加速求解MINLP问题的SQP并行算法[J]. 化工学报, 2012, 63(11): 3597-3601.

KANG Lixia, ZHANG Yanrong, TANG Yazhe, LIU Yongzhong. Paralleled SQP algorithm for solution of MINLP problems based on GPU acceleration[J]. CIESC Journal, 2012, 63(11): 3597-3601.

参考文献 22

[1]	Barton P I,Lee C K.Design of process operations using hybrid dynamic optimization[J].Computers & Chemical Engineering,2004,28(6/7):955-969
[2]	Grossmann I E,Caballero J A,Yeomans H.Mathematical programming approaches to the synthesis of chemical process systems[J].Korean Journal of Chemical Engineering,1999,16(4):407-426
[3]	Lee S,Grossmann I E.A global optimization algorithm for nonconvex generalized disjunctive programming and applications to process systems[J].Computers & Chemical Engineering,2001,25(11/12):1675-1697
[4]	Kallrath J.Mixed integer optimization in the chemical process industry[J].Trans. IChemE,2000,78(Part A):809-822
[5]	Schulz E,Diaz M,Bandoni J.Supply chain optimization of large-scale continuous processes[J].Computers and Chemical Engineering,2005,26(6):1305-1316
[6]	Furman K C,Sahinidis N V.A critical review and annotated bibliography for heat exchanger network synthesis in the 20th century[J].Industrial & Engineering Chemistry Research,2002,41(10):2335-2370
[7]	Grossmann I E,Biegler L T.Part Ⅱ.Future perspective on optimization[J].Computers & Chemical Engineering,2004,28(8):1193-1218
[8]	Kallrath J.Solving planning and design problems in the process industry using mixed integer and global optimization[J].Annals of Operations Research,2005,140(1):339-373
[9]	Biegler L T,Grossmann I E.Retrospective on optimization[J].Computers & Chemical Engineering,2004,28(8):1169-1192
[10]	Duran M,Grossmann I.A mixed-integer nonlinear programming algorithm for process systems synthesis[J].AIChE Journal,1986,32(4):592-606
[11]	Hartwich A,Stockmann K,Terboven C,et al.Parallel sensitivity analysis for efficient large-scale dynamic optimization[J].Optimization and Engineering,2011,12(4):489-508
[12]	Wah B,Chen Y.Constraint partitioning in penalty formulations for solving temporal planning problems[J].Artificial Intelligence,2006,170(3):187-231
[13]	Björkqvist J,Westerlund T.Parallel solution of disjunctive MINLP problems[J].Chemical Engineering Communications,2001,185(1):115-124
[14]	Cheng Xu(程序),Wu Cheng(吴澄).Decomposition and optimization methods for large-scale project schedules[J].Journal of Tsinghua University:Sci. & Tech.(清华大学学报:自然科学版),2009,49(1):153-156
[15]	Owens J D,Houston M,Luebke D,Green S,Stone J E,Phillips J C.GPU computing[J].Proceedings of the IEEE,2008,96(5):879-899
[16]	Garland M,Grand S,Nickolls J,Anderson J,Hardwick J,Morton S,Philips E,Zhang Y,Volkov V.Parallel computing experiences with CUDA[J].IEEE Micro.,2008,28(4):13-27
[17]	Wang R,Zhou K,Pan M,Bao H.An efficient GPU-based approach for interactive global illumination[J].ACM Transactions on Graphics(TOG),2009,28(3):1-8
[18]	Yan D,Cao H,Dong X,Zhang B,Zhang X.Optimizing algorithm of sparse linear systems on GPU//Proceeding of 2011 Sixth Annual Chinagrid Conference[C].Liaoning,China,2011:174-179
[19]	Munawar A,Wahib M,Munetomo M,et al.Advanced genetic algorithm to solve MINLP problems over GPU//Proceeding of the IEEE Congress of Evolutionary Computation.New Orleans,LA,2011:318-325
[20]	Wang Jing(汪靖),Wu Zhijian(吴志建).Opposition-based particle swarm optimization for solving large scale optimization problems on GPU[J].Journal of Wuhan University:Natural Science(武汉大学学报:理学版),2011,57(2):148-154
[21]	Grossmann I E.Review of nonlinear mixed-integer and disjunctive programming techniques[J].Optimization and Engineering,2002,3(3):227-252
[22]	Rosenthal R E.Gams:A User’s Guide[M].Washington D C:GAMS Development Corporation,2010:166

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

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

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献 22

相关文章 15

编辑推荐

Metrics

本文评价

[1]	温凯杰, 郭力, 夏诏杰, 陈建华. 一种耦合CFD与深度学习的气固快速模拟方法[J]. 化工学报, 2023, 74(9): 3775-3785.
[2]	薛涵文, 聂峰, 赵延兴, 董学强, 郭浩, 沈俊, 公茂琼. 基于流型的R290水平管内流动沸腾压降实验研究[J]. 化工学报, 2022, 73(11): 4903-4916.
[3]	杨遂军, 丁炯, 许启跃, 叶树亮, 郭子超, 陈网桦. 绝热加速量热无模型方法动力学预测[J]. 化工学报, 2022, 73(11): 4987-4997.
[4]	张浩, 王姣, 马挺, 李馨怡, 刘军, 王秋旺. 超重条件下泡沫石墨-石蜡相变传热实验研究[J]. 化工学报, 2021, 72(9): 4523-4530.
[5]	彭肖祎, 董轩, 廖祖维, 杨遥, 孙婧元, 蒋斌波, 王靖岱, 阳永荣. 数学规划与图形方法相结合设计热集成用水网络[J]. 化工学报, 2021, 72(2): 1047-1058.
[6]	杨蕊, 庄钰, 邸楠茜, 都健. 基于超结构法的热集成间接式功交换网络综合[J]. 化工学报, 2019, 70(12): 4689-4697.
[7]	丁炯, 陈琪, 许启跃, 杨遂军, 叶树亮. 融合C80数据的绝热加速量热法热惯量因子修正[J]. 化工学报, 2019, 70(1): 417-424.
[8]	胡明涛, 鞠鹏飞, 赵旭辉, 唐聿明, 左禹. 不同加速试验对环氧/聚氨酯涂层失效机制的影响[J]. 化工学报, 2018, 69(8): 3548-3556.
[9]	张凌翔, 周克毅, 徐奇, 司晓东, 林彤. 90°弯管流动加速腐蚀的实验和数值模拟[J]. 化工学报, 2018, 69(12): 5173-5181.
[10]	曹健, 牟鹏, 耿志强, 朱群雄. 工业系统超结构模型应用研究进展[J]. 化工学报, 2017, 68(3): 801-810.
[11]	杨新, 陈鸿伟, 梁占伟, 许文良, 孙超. 基于气固两相流的双循环流化床提升管压降模型的预测和实验研究[J]. 化工学报, 2017, 68(12): 4585-4591.
[12]	董泽, 陈利平, 陈网桦, 马莹莹. 密闭容器内失控反应超压的数学建模及其在压力泄放中的应用[J]. 化工学报, 2017, 68(11): 4453-4460.
[13]	郭子超, 郝琳, 卫宏远. 一种计算最大反应速率到达时间的新方法[J]. 化工学报, 2016, 67(S1): 22-27.
[14]	姜楠, 刘永忠, 朱天鸿. 换热网络合成问题的并行BB/SQP混合算法[J]. 化工学报, 2016, 67(12): 5169-5175.
[15]	魏彤彤, 钱新明, 袁梦琦. 酸、碱污染物对过氧化苯甲酸叔丁酯热危险性影响[J]. 化工学报, 2015, 66(10): 3931-3939.