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