一个求解池化问题的二阶锥逼近算法

doi:10.15960/j.cnki.issn.1007-6093.2020.02.005

运筹学学报 ›› 2020, Vol. 24 ›› Issue (2): 61-72.doi: 10.15960/j.cnki.issn.1007-6093.2020.02.005

一个求解池化问题的二阶锥逼近算法

任烨权¹, 白延琴^1,*, 李倩², 余长君¹, 张连生¹

1. 上海大学理学院数学系, 上海 200444;
2. 上海工程技术大学理学院, 上海 200335

收稿日期:2020-03-01 发布日期:2020-06-13
通讯作者: 白延琴 E-mail:yqbai@t.shu.edu.cn
基金资助:
国家自然科学基金（No.11771275）

A second-order cone programming algorithm for pooling problem

REN Yequan¹, BAI Yanqin^1,*, LI Qian², YU Changjun¹, ZHANG Liansheng¹

1. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China;
2. College of Sciences, Shanghai University of Engineering Science, Shanghai 200335, China

Received:2020-03-01 Published:2020-06-13

摘要/Abstract

摘要： 池化问题是工业生产计划中的一个重要问题.通过对原料的合理混合，以混合过程的容量及平衡约束等作为约束条件，要求总体生产成本最低.池化问题的优化模型类似于最小费用流问题.然而，由于该问题的复杂性，池化问题即便在只有一个成分约束的情况下依然是强NP-难问题.基于戴彧虹等提出的优化模型，现对模型进行了一系列的转化.首先将模型等价转化成二次非凸优化模型，其次通过对约束的松弛和内逼近分别给出两个近似的二阶锥规划模型.为了获得模型的全局最优解，采用分支定界的策略，通过求解上下界来逼近原问题的最优解.最后，通过算例开展了数值实验，验证了改进模型和算法的有效性.

关键词: 池化问题, 分支定界法, 二阶锥规划

Abstract: The pooling problem plays an important role in industrial production planning. The optimization model of this problem is similar to the minimum cost problem. However, due to the complexity of the problem, the pooling problem is strong NP-hard even with only one quality. In this paper, based on the optimization model proposed by Dai, we reformulate the model step by step. First, we reformulated the primal model into a quadratic non-convex optimization model equivalently. Then, we relaxed and inner approximate quadratic non-convex optimization model into both second-order cone programming problem, respectively. To solve both second-order cone programming problem, we used the branch and bound method to approximate the optimal solution of the original problem by solving the upper and lower bounds. Finally, we carried out the numerical experiments by using seven examples to demonstrate the effectiveness of our models and the algorithm.

Key words: pooling problem, branch-and-bound, second-order cone program

中图分类号:

O224

任烨权, 白延琴, 李倩, 余长君, 张连生. 一个求解池化问题的二阶锥逼近算法[J]. 运筹学学报, 2020, 24(2): 61-72.

REN Yequan, BAI Yanqin, LI Qian, YU Changjun, ZHANG Liansheng. A second-order cone programming algorithm for pooling problem[J]. Operations Research Transactions, 2020, 24(2): 61-72.

参考文献

[1] Haverly C A. Studies of the behavior of recursion for the pooling problem[J]. ACM SIGMAP Bulletin, 1978, 25(25):19-28.
[2] Baker T E, Lasdon L S. Successive linear programming at Exxon[J]. Management Science, 1985, 31(3):264-274.
[3] DeWitt C W, Lasdon L S, Waren A D, et al. OMEGA:An improved gasoline blending system for texaco[J]. Interfaces, 1989, 19(1):85-101.
[4] Galan B, Grossmann I E. Optimal design of distributed wastewater treatment networks[J]. Industrial & Engineering Chemistry Research, 1998, 37(10):4036-4048.
[5] Misener R, Floudas C A. Global optimization of large-scale generalized pooling problems:Quadratically constrained MINLP models[J]. Industrial & Engineering Chemistry Research, 2010, 49(11):5424-5438.
[6] Boland N, Kalinowski T, Rigterink F. New multi-commodity flow formulations for the pooling problem[J]. Journal of Global Optimization, 2016, 66(4):669-710.
[7] 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.
[8] Alfaki M, Haugland D. Strong formulations for the pooling problem[J]. Journal of Global Optimization, 2012, 56(3):897-916.
[9] Haverly C A. Behavior of recursion model-more studies[J]. ACM SIGMAP Bulletin, 1979, 26(26):22-28.
[10] Lasdon L S, Waren A D, Sarkar S, et al. Solving the pooling problem using generalized reduced gradient and successive linear programming algorithms[J]. ACM SIGMAP Bulletin, 1979, 27(27):9-15.
[11] Dai Y H, Diao R, Fu K. Complexity analysis and algorithm design of pooling problem[J]. Journal of the Operations Research Society of China, 2018, 6(2):249-266.
[12] Visweswaran V, Floudas C A. New formulations and branching strategies for the GOP algorithm[J]. Nonconvex Optimization and its Applications, 1996, 75-109.
[13] Foulds L R, Haugland D, Jornsten K. A bilinear approach to the pooling problem[J]. Optimization, 1992, 24(1-2):165-180.
[14] Adhya N, Tawarmalani M, Sahinidis N V. A Lagrangian approach to the pooling problem[J]. Industrial & Engineering Chemistry Research, 1999, 38(5):1956-1972.
[15] Ben-Tal A, Eiger G, Gershovitz V. Global minimization by reducing the duality gap[J]. Mathematical Programming, 1994, 63(1-3):193-212.
[16] Kimizuka M, Kim S, Yamashita M. Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods[J]. Journal of Global Optimization, 2019, 75:631-654.
[17] Pham V, Laird C, El-Halwagi M. Convex hull discretization approach to the global optimization of pooling problems[J]. Industrial & Engineering Chemistry Research, 2009, 48(4):1973-1979.
[18] Gupte A, Ahmed S, Dey S S, et al. Relaxations and discretizations for the pooling problem[J]. Journal of Global Optimization, 2016, 67(3):631-669.
[19] Body S, Vandenberghe L. Convex Optimization[M]. Cambridge:Cambridge University Press, 2004.
[20] Li Y J, Zhu S S, Li D H, et al. Active allocation of systematic risk and control of risk sensitivity in portfolio optimization[J]. European Journal of Operational Research, 2013, 228(3):556-570.

一个求解池化问题的二阶锥逼近算法

A second-order cone programming algorithm for pooling problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	曾友芳, 唐春明. 二阶锥规划一个超线性收敛的非内部连续化算法[J]. 运筹学学报, 2015, 19(1): 18-30.
[2]	张景, 白延琴. 二阶锥规划的基于自协调指数核函数的原始-对偶内点算法[J]. 运筹学学报, 2014, 18(4): 11-24.