A polynomially solvable case of the pooling problem. (English) Zbl 1365.90212

Summary: Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomial time by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border between (strongly) NP-hard and polynomially solvable cases of the pooling problem.


90C26 Nonconvex programming, global optimization
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI arXiv


[1] Alfaki, M; Haugland, D, A multi-commodity flow formulation for the generalized pooling problem, J. Glob. Optim., 56, 917-937, (2013) · Zbl 1272.90103
[2] Alfaki, M; Haugland, D, Strong formulations for the pooling problem, J. Glob. Optim., 56, 897-916, (2013) · Zbl 1272.90054
[3] Audet, C; Brimberg, J; Hansen, P; Digabel, S; Mladenović, N, Pooling problem: alternate formulations and solution methods, Manag. Sci., 50, 761-776, (2004) · Zbl 1232.90349
[4] Ben-Tal, A; Eiger, G; Gershovitz, V, Global minimization by reducing the duality gap, Math. Program., 63, 193-212, (1994) · Zbl 0807.90101
[5] Boland, N; Kalinowski, T; Rigterink, F; Weber, T (ed.); McPhee, MJ (ed.); Anderssen, RS (ed.), Discrete flow pooling problems in coal supply chains, 1710-1716, (2015), Gold Coast
[6] Boland, N; Kalinowski, T; Rigterink, F, New multi-commodity flow formulations for the pooling problem, J. Glob. Optim. Adv. Online Publ., (2016) · Zbl 1369.90132
[7] Boland, N., Kalinowski, T., Rigterink, F., Savelsbergh, M.: A special case of the generalized pooling problem arising in the mining industry. Optimization Online e-prints. (2015). http://www.optimization-online.org/DB_HTML/2015/07/5025.html · Zbl 1360.90258
[8] Buck, RC, Partition of space, Am. Math. Mon., 50, 541-544, (1943) · Zbl 0061.30609
[9] Witt, CW; Lasdon, LS; Waren, AD; Brenner, DA; Melhem, SA, OMEGA: an improved gasoline blending system for texaco, Interfaces, 19, 85-101, (1989)
[10] Dey, SS; Gupte, A, Analysis of MILP techniques for the pooling problem, Oper. Res., 63, 412-427, (2015) · Zbl 1327.90351
[11] Gupte, A., Ahmed, S., Dey, S. S., Cheon, M. S.: Relaxations and discretizations for the pooling problem. J. Glob. Optim., to appear. Preprint: http://www.optimization-online.org/DB_HTML/2015/04/4883.html · Zbl 1392.90117
[12] Haugland, D; Casado, LG (ed.); García, I (ed.); Hendrix, EMT (ed.), The hardness of the pooling problem, 29-32, (2014), Spain
[13] Haugland, D, The computational complexity of the pooling problem, J. Glob. Optim., 64, 199-215, (2015) · Zbl 1360.90258
[14] Haugland, D; Hendrix, EMT, Pooling problems with polynomial-time algorithms, J. Optim. Theory Appl., (2016) · Zbl 1346.90681
[15] Haverly, CA, Studies of the behavior of recursion for the pooling problem, SIGMAP Bull., 25, 19-28, (1978)
[16] Rigby, B; Lasdon, LS; Waren, AD, The evolution of texaco’s blending systems: from OMEGA to starblend, Interfaces, 25, 64-83, (1995)
[17] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. Nonconvex Optimization and its Applications, vol. 65. Springer, New York (2002) · Zbl 1031.90022
[18] Visweswaran, V; Floudas, CA (ed.); Pardalos, PM (ed.), MINLP: applications in blending and pooling problems, 2114-2121, (2009), New York
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.