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

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

Abstract

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

CLC Number:

O224

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	ZENG Youfang, TANG Chunming. A non-interior-point continuous algorithm with superlinear convergence for second-order cone programming [J]. Operations Research Transactions, 2015, 19(1): 18-30.
[2]	PAN Shao-Rong, ZHANG Li-Wei. Fritz-John Condition for a Class of Nondifferntiable Optimization [J]. Operations Research Transactions, 2011, 15(2): 77-84.