Strong formulations for the pooling problem. (English) Zbl 1272.90054

Summary: The pooling problem is a well-studied global optimization problem with applications in oil refining and petrochemical industry. Despite the strong NP-hardness of the problem, which is proved formally in this paper, most instances from the literature have recently been solved efficiently by use of strong formulations. The main contribution from this paper is a new formulation that proves to be stronger than other formulations based on proportion variables. Moreover, we propose a promising branching strategy for the new formulation and provide computational experiments confirming the strength of the new formulation and the effectiveness of the branching strategy.


90C26 Nonconvex programming, global optimization
90C60 Abstract computational complexity for mathematical programming problems


Full Text: DOI Link


[1] Adhya, N.; Tawarmalani, M.; Sahinidis, N.V., A Lagrangian approach to the pooling problem, Ind. Eng. Chem. Res., 38, 1956-1972, (1999)
[2] Al-Khayyal, F.A.; Falk, J.E., Jointly constrained biconvex programming, Math. Oper. Res., 8, 273-286, (1983) · Zbl 0521.90087
[3] Almutairi, H.; Elhedhli, S., A new Lagrangian approach to the pooling problem, J. Glob. Optim., 45, 237-257, (2009) · Zbl 1193.90189
[4] Audet, C.; Brimberg, J.; Hansen, P.; Le Digabel, S.; Mladenović, N., Pooling problem: alternate formulations and solution methods, Manag. Sci., 50, 761-776, (2004) · Zbl 1232.90349
[5] Audet, C.; Hansen, P.; Jaumard, B.; Savard, G., A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Math. Program., 87, 131-152, (2000) · Zbl 0966.90057
[6] Baker, T.E.; Lasdon, L.S., Successive linear programming at exxon, Manag. Sci., 31, 264-274, (1985) · Zbl 0608.90090
[7] Ben-Tal, A.; Eiger, G.; Gershovitz, V., Global minimization by reducing the duality gap, Math. Program., 63, 193-212, (1994) · Zbl 0807.90101
[8] Floudas, C.A.; Aggarwal, A., A decomposition strategy for global optimum search in the pooling problem, Oper. Res. J. Comput., 2, 225-235, (1990) · Zbl 0755.90091
[9] Floudas, C.A.; Visweswaran, V., A global optimization algorithm (GOP) for certain classes of nonconvex NLPs-I. theory, Comput. Chem. Eng., 14, 1397-1417, (1990)
[10] Foulds, L.R.; Haugland, D.; Jörnsten, K., A bilinear approach to the pooling problem, Optimization, 24, 165-180, (1992) · Zbl 0817.90073
[11] Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979) · Zbl 0411.68039
[12] Gounaris, C.E.; Misener, R.; Floudas, C.A., Computational comparison of piecewise-linear relaxations for pooling problems, Ind. Eng. Chem. Res., 48, 5742-5766, (2009)
[13] Griffith, R.E.; Stewart, R.A., A nonlinear programming technique for the optimization of continuous processing systems, Manag. Sci., 7, 379-392, (1961) · Zbl 0995.90610
[14] Haverly, C.A., Studies of the behavior of recursion for the pooling problem, ACM SIGMAP Bull., 25, 19-28, (1978)
[15] Haverly, C.A., Behavior of recursion model-more studies, ACM SIGMAP Bull., 26, 22-28, (1979)
[16] Karuppiah, R.; Grossmann, I.E., Global optimization for the synthesis of integrated water systems in chemical processes, Comput. Chem. Eng., 30, 150-173, (2006)
[17] Liberti, L.; Pantelides, C.C., An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms, J. Glob. Optim., 36, 161-189, (2006) · Zbl 1131.90045
[18] McCormick, G.P., Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[19] Meyer, C.A.; Floudas, C.A., Global optimization of a combinatorially complex generalized pooling problem, AIChE J., 52, 1027-1037, (2006)
[20] Misener, R.; Gounaris, C.E.; Floudas, C.A., Mathematical modeling and global optimization of large-scale extended pooling problems with the (EPA) complex emissions constraints, Comput. Chem. Eng., 34, 1432-1456, (2010)
[21] Palacios-Gomez F. Lasdon, L.; Lasdon, F.; Engquist, M., Nonlinear optimization by successive linear programming, Manag. Sci., 28, 1106-1120, (1982) · Zbl 0507.90080
[22] Quesada, I.; Grossmann, I.E., Global optimization of bilinear process networks with multicomponent flows, Comput. Chem. Eng., 19, 1219-1242, (1995)
[23] Ryoo, H.S.; Sahinidis, N.V., Global optimization of nonconvex NLPs and MINLPs with applications in process design, Comput. Chem. Eng., 19, 551-566, (1995)
[24] Sahinidis, N.V., BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[25] Sahinidis, N.V.; Tawarmalani, M., Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints, J. Glob. Optim., 32, 259-280, (2005) · Zbl 1080.90087
[26] Sarker, R.A.; Gunn, E.A., A simple SLP algorithm for solving a class of nonlinear programs, Eur. J. Oper. Res., 101, 140-154, (1997) · Zbl 0916.90247
[27] Shectman, J.P.; Sahinidis, N.V., A finite algorithm for global minimization of separable concave programs, J. Glob. Optim., 12, 1-35, (1998) · Zbl 0906.90159
[28] Sherali H.D., Adams W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1999) · Zbl 0926.90078
[29] Sherali, H.D.; Adams, W.P.; Driscoll, P.J., Exploiting special structures in constructing a hierarchy of relaxations for 0-1 mixed integer problems, Oper. Res., 46, 396-405, (1998) · Zbl 0979.90090
[30] Visweswaran, V.; Floudas, C.A., A global optimization algorithm (GOP) for certain classes of nonconvex NLPs-II. application of theory and test problems, Comput. Chem. Eng., 14, 1419-1434, (1990)
[31] Zhang, J.H.; Kim, N.H.; Lasdon, L., An improved successive linear-programming algorithm, Manag. Sci., 31, 1312-1331, (1985) · Zbl 0601.90128
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.