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

doi:10.3969/j.issn.0438-1157.2012.11.032

CIESC Journal ›› 2012, Vol. 63 ›› Issue (11): 3597-3601.DOI: 10.3969/j.issn.0438-1157.2012.11.032

Previous Articles Next Articles

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.

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

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

1. 西安交通大学化学工程系, 陕西西安 710049;
2. 西安交通大学计算机科学与技术系, 陕西西安 710049;
3. 热流科学与工程教育部重点实验室, 陕西西安 710049

通讯作者: 刘永忠
作者简介:康丽霞(1989-),女,博士研究生。
基金资助:
陕西省自然科学基金项目(2012JM2001);国家自然科学基金重点项目(20936004);中央高校基本科研业务费专项资金资助项目。

Abstract

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

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

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

CLC Number:

TQ021.8

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.

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

References 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

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

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

PDF (PC)

Knowledge

Cited

Abstract

Cite this article

share this article

References 22

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Kaijie WEN, Li GUO, Zhaojie XIA, Jianhua CHEN. A rapid simulation method of gas-solid flow by coupling CFD and deep learning [J]. CIESC Journal, 2023, 74(9): 3775-3785.
[2]	Hanwen XUE, Feng NIE, Yanxing ZHAO, Xueqiang DONG, Hao GUO, Jun SHEN, Maoqiong GONG. Experimental study of flow boiling pressure drop of R290 in a horizontal tube based on flow pattern [J]. CIESC Journal, 2022, 73(11): 4903-4916.
[3]	Hao ZHANG, Jiao WANG, Ting MA, Xinyi LI, Jun LIU, Qiuwang WANG. Experimental investigation on phase change heat transfer of paraffin composited with porous graphite under supergravity [J]. CIESC Journal, 2021, 72(9): 4523-4530.
[4]	CHEN Qin, QI Hong, ZHANG Zeyu, RUAN Liming. Radiative properties reconstruction of disperse media based on SQP algorithm [J]. CIESC Journal, 2017, 68(S1): 37-42.
[5]	CAO Jian, MU Peng, GENG Zhiqiang, ZHU Qunxiong. Research progress and application of superstructure model for industrial systems [J]. CIESC Journal, 2017, 68(3): 801-810.
[6]	YANG Xin, CHEN Hongwei, LIANG Zhanwei, XU Wenliang, SUN Chao. Model prediction and experimental study of pressure drop in double circulating fluidized bed risers of gas-solid two-phase flow [J]. CIESC Journal, 2017, 68(12): 4585-4591.
[7]	JIANG Nan, LIU Yongzhong, ZHU Tianhong. Parallel algorithm of hybrid BB/SQP for heat exchanger network synthesis [J]. CIESC Journal, 2016, 67(12): 5169-5175.
[8]	CHEN Shuai, LUO Na. Adaptive competitive swarm optimization for heat exchanger networks without split streams [J]. CIESC Journal, 2016, 67(11): 4716-4723.
[9]	WU Min，XIAO Wu，HE Gaohong. Analysis of equipment and operating costs of the pump and optimization of heat exchanger network [J]. Chemical Industry and Engineering Progree, 2014, 33(03): 599-604.
[10]	WAN Jiwei, NIU Zhengming, LIAO Weili, NIU Zhunong. Mixing mechanism of multiphase flow and acceleration performance in single inlet rear-mixed jet flow crushing [J]. CIESC Journal, 2013, 64(7): 2418-2427.
[11]	LI Hong, WU Lianying, SHANG Fengying, LV Shiqiang, HU Yangdong. Optimal plan and scheduling of multi-stage drying system [J]. CIESC Journal, 2012, 63(7): 2136-2142.
[12]	JIAO Yunqiang, SU Hongye, HOU Weifeng. Optimal scheduling of hydrogen system in refinery and its application [J]. CIESC Journal, 2011, 62(8): 2101-2107.
[13]	CAI Kang, GUAN Xin, LUO Xing, Georg Fieg. Optimization of large-scale heat exchanger networks by evolution of sub-networks [J]. CIESC Journal, 2009, 60(9): 2265-2270.
[14]	. Flowsheet modeling and simulation for an industrial soda plant [J]. , 2007, 58(3): 692-697.
[15]	DONG Fenglian，YUAN Xigang，LUO Yiqing. Research on heat integrated complex distillation system synthesis [J]. , 2007, 26(2): 276-.