The pooling problem arises in the chemical process and petroleum industries. It is a generalization of a minimum cost network flow problem where products possess different specifications (e.g. sulphur concentration). In a pooling problem, flow streams from different sources are mixed in intermediate tanks (pools) and blended again in the terminal points. At the pools and terminals, the quality of a mixture is given as the volume (weight) average of the qualities of the flow streams that go into them.
There are three types of tanks: inputs or sources, which are the tanks to store the raw materials, pools, to blend incoming flow streams and make new compositions, and outputs or terminals, to store the final products. According to the links among different tanks, pooling problems can be classified into three classes:
- Standard pooling problem: in this class there is no flow stream among the pools. It means that the flow streams are in the form of input-output, input-pool and pool-output.
- Generalized pooling problem: here, flow streams between the pools are allowed.
- Extended pooling problem: here, the problem is to maximize the profit (minimize the cost) on a standard pooling problem network while complying with constraints on nonlinearly blending fuel qualities such as those in the Environmental Protection Agency (EPA) Title 40 Code of Federal Regulations Part 80.45.
Optimization models and methods
There are many equivalent mathematical formulations for the pooling problem, such as P-, Q-, PQ- and HYB- formulations, and all of them may be formulated as nonconvex (bilinear) problems, and consequently the problem can possibly have many local optima. More information about different formulations may be found in [4].
Solution methods and software
Despite the strong N P-hardness, proved in [2], much progress in solving small to moderate size instances to global optimality has been made since 1978, when Harvely [5] described the P-formulation and solved small standard pooling problems using recursive linear programming. Today, there are many methods in the literature; a survey is given in [9]. A common approach is to construct good lower and upper bounds for use in a branch-and-bound framework; see e.g. Foulds et al. [3]. Adhya et al. [1] introduced a Lagrangian approach to get a tighter lower bounds. The APOGEE software by Misener et al. [8] uses a piecewise linear relaxation for the bilinear terms by introducing a logarithmic number of binary variables. The software GloMIQO [7] may be used to solve mixed-integer, quadratically-constrained, quadratic programs, making it suitable for solving pooling problems.
Two interesting generalizations of the pooling problem are:
- more general networks where other types of units than pools are also present, e.g. units that extract pollutants. Mathematically, this generalisation falls within the framework of so-called wastewater management networks; see e.g. [6].
- treating the network topology as a decision variable, as done in [8].
References
[1] N. Adhya, M. Tawarmalani, and N. V. Sahinidis. A Lagrangian approach to the pooling problem. Industrial & Engineering Chemistry Research, 38(5):1956–1972, 1999.
[2] M. Alfaki. Models and solution methods for the pooling problem. Ph.D. thesis, University of Bergen, 2012.
[3] L.R. Foulds, D. Haugland, and K. J ̈ornsten. A bilinear approach to the pooling problem. Optimization, 24(1-2):165–180, 1992.
[4] A. Gupte, Sh. Ahmed, S. S. Dey, and M. S. Cheon. Pooling problems: relaxations and discretizations. Optimization Online, 2013.
[5] C. A. Haverly. Studies of the behavior of recursion for the pooling problem. ACM SIGMAP Bulletin, (25):19–28, 1978.
[6] R. Karuppiah and I.E. Grossmann. Global optimization for the synthesis of integrated water systems in chemical processes. Computers and Chemical Engineering, 30(4):650–673, 2006.
[7] R. Misener and Ch. A. Floudas. GloMIQO: Global mixed-integer quadratic optimizer. J. of Global Optimization, 57(1):3–50, 2013.
[8] R. Misener, J. P. Thompson, and Ch. A. Floudas. APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Computers & Chemical Engineering, 35(5):876–892, 2011.
[9] Ruth Misener and Christodoulos A. Floudas. Advances for the pooling problem: Modeling, global optimization, and computational studies. Applied and Computational Mathematics, 8(1), 3-22, 2009.
Contributors:
Prof. Etienne de Klerk, Tilburg University
Dr. Ahmadreza Marandi, Tilburg University
Dr. Lars Schewe, Universität Erlangen-Nürnberg
Prof. Kees Vuik, Delft University