Abstract
The pooling problem is an extension of the minimum cost network flow problem where the composition of the flow depends on the sources from which it originates. At each source, the composition is known. In all other nodes, the proportion of any component is given as a weighted average of its proportions in entering flow streams. The weights in this average are simply the arc flow. At the terminals of the network, there are bounds on the relative content of the various components. Such problems have strong relevance in e.g. planning models for oil refining, and in gas transportation models with quality constraints at the reception side. Although the pooling problem has bilinear constraints, much progress in solving a class of instances to global optimality has recently been made. Most of the approaches are however restricted to networks where all directed paths have length at most three, which means that there is no connection between pools. In this work, we generalize one of the most successful formulations of the pooling problem, and propose a multi-commodity flow formulation that makes no assumptions on the network topology. We prove that our formulation has stronger linear relaxation than previously suggested formulations, and demonstrate experimentally that it enables faster computation of the global optimum.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adhya N., Sahinidis N.V., Tawarmalani M.: A Lagrangian approach to the pooling problem. Ind. Eng. Chem. Res. 38(5), 1956–1972 (1999)
Al-Khayyal F.A., Falk J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983)
Alfaki, M., Haugland, D.: Strong formulations for the pooling problem. J. Glob. Optim. (The current issue). doi:10.1007/s10898-012-9875-6 (2012)
Audet C., Brimberg J., Hansen P., Le Digabel S., Mladenović N.: Pooling problem: alternate formulations and solution methods. Manag. Sci. 50(6), 761–776 (2004)
Ben-Tal A., Eiger G., Gershovitz V.: Global minimization by reducing the duality gap. Math. Program. 63(1), 193–212 (1994)
Foulds L.R., Haugland D., Jörnsten K.: A bilinear approach to the pooling problem. Optimization 24(1), 165–180 (1992)
Gounaris C.E., Misener R., Floudas C.A.: Computational comparison of piecewise linear relaxation for pooling problems. Ind. Eng. Chem. Res. 48(12), 5742–5766 (2009)
Guisewite G.M.: Network problems. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization, pp. 609–648. Kluwer, Dordrecht (1995)
Haverly C.A.: Studies of the behavior of recursion for the pooling problem. ACM SIGMAP Bull. 25, 19–28 (1978)
Haverly C.A.: Behavior of recursion model-more studies. ACM SIGMAP Bull. 26, 22–28 (1979)
Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. Kluwer, Dordrecht, The Netherlands (2000)
Karuppiah R., Grossmann I.E.: Global optimization for the synthesis of integrated water systems in chemical processes. J. Comput. Chem. Eng. 30(4), 650–673 (2006)
Li X., Armagan E., Tomasgard A., Barton P.I.: Stochastic pooling problem for natural gas production network design and operation under uncertainty. AIChE J. 57(8), 2120–2135 (2011)
Main R.A.: Large recursion models: practical aspects of recursion techniques. In: Ciriani, T., Leachman, R. (eds.) Optimization in Industry: Mathematical Programming and Modeling Techniques in Practice, pp. 241–249. Wiley, New York (1993)
McCormick G.P.: Computability of global solutions to factorable nonconvex programs: part I - convex underestimating problems. Math. Program. 10(1), 147–175 (1976)
Meyer C.A., Floudas C.A.: Global optimization of a combinatorially complex generalized pooling problem. AIChE J. 52(3), 1027–1037 (2006)
Misener R., Floudas C.A.: Advances for the pooling problem: modeling, global optimization, and computational studies. Appl. Comput. Math. 8(1), 3–22 (2009)
Misener R., Floudas C.A.: Global optimization of large-scale generalized pooling problems: quadratically constrained MINLP models. Ind. Eng. Chem. Res. 49(11), 5424–5438 (2010)
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. J. Comput. Chem. Eng. 34, 1432–1456 (2010)
Sahinidis N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8(2), 201–205 (1996)
Sahinidis N.V., Tawarmalani M.: Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints. J. Glob. Optim. 32(2), 259–280 (2005)
Sherali H.D.: Tight relaxations for nonconvex optimization problems using the reformulation-linearization/convexification technique (RLT). In: Pardalos, P.M., Romeijn, E. (eds.) Handbook of Global Optimization, vol. 2, pp. 1–164. Kluwer, Dordrecht, The Netherlands (2002)
Sherali H.D., Adams W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht, The Netherlands (1999)
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(3), 396–405 (1998)
Tawarmalani M., Sahinidis N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer, Dordrecht, The Netherlands (2002)
Wicaksono D.S., Karimi I.A.: Piecewise MILP under- and overestimators for global optimization of bilinear programs. AIChE J. 54(4), 991–1008 (2008)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Alfaki, M., Haugland, D. A multi-commodity flow formulation for the generalized pooling problem. J Glob Optim 56, 917–937 (2013). https://doi.org/10.1007/s10898-012-9890-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-012-9890-7