The pooling problem arises in the chemical process and petroleum industr= ies. It is a generalization of a minimum cost network flow problem where pr= oducts possess different specifications (e.g. sulphur concentration). In a = pooling problem, flow streams from different sources are mixed in intermedi= ate tanks (pools) and blended again in the terminal points. At the pools an= d terminals, the quality of a mixture is given as the volume (weight) avera= ge of the qualities of the flow streams that go into them.

There are three types of tanks: inputs or sources, which are the tanks t= o store the raw materials, pools, to blend incoming flow streams and make n= ew compositions, and outputs or terminals, to store the final products. Acc= ording to the links among different tanks, pooling problems can be classifi= ed into three classes:

- Standard pooling problem: in this class there is no flow stream among t= he pools. It means that the flow streams are in the form of input-output, i= nput-pool and pool-output.
- Generalized pooling problem: here, flow streams between the pools are a= llowed.
- Extended pooling problem: here, the problem is to maximize the profit (= minimize the cost) on a standard pooling problem network while complying wi= th 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 prob= lem, such as P-, Q-, PQ- and HYB- formulations, and all of them may be form= ulated as nonconvex (bilinear) problems, and consequently the problem can p= ossibly have many local optima. More information about different formulatio= ns 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 standar= d pooling problems using recursive linear programming. Today, there are man= y 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 fra= mework; see e.g. Foulds et al. [3]. Adhya et al. [1] introduced a Lagrangia= n 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 intro= ducing a logarithmic number of binary variables. The software GloMIQO [7] m= ay be used to solve mixed-integer, quadratically-constrained, quadratic pro= grams, 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 pr= esent, e.g. units that extract pollutants. Mathematically, this generalisat= ion 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, 3= 8(5):1956=E2=80=931972, 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 =CC=88ornsten. A bilinear approac= h to the pooling problem. Optimization, 24(1-2):165=E2=80=93180, 1992.

[4] A. Gupte, Sh. Ahmed, S. S. Dey, and M. S. Cheon. Pooling problems: r= elaxations and discretizations. Optimization Online, 2013.

[5] C. A. Haverly. Studies of the behavior of recursion for the pooling = problem. ACM SIGMAP Bulletin, (25):19=E2=80=9328, 1978.

[6] R. Karuppiah and I.E. Grossmann. Global optimization for the synthes= is of integrated water systems in chemical processes. Computers and Chemica= l Engineering, 30(4):650=E2=80=93673, 2006.

[7] R. Misener and Ch. A. Floudas. GloMIQO: Global mixed-integer quadrat= ic optimizer. J. of Global Optimization, 57(1):3=E2=80=9350, 2013.

[8] R. Misener, J. P. Thompson, and Ch. A. Floudas. APOGEE: Global optim= ization of standard, generalized, and extended pooling problems via linear = and logarithmic partitioning schemes. Computers & Chemical Engineering,= 35(5):876=E2=80=93892, 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.<= /p>

**Contributors**:

Prof. Etienne de Klerk, Tilburg University

Dr. Ahmadreza Marandi, Tilburg Uni=
versity

Dr. Lars Schewe, Universit=C3=A4t =
Erlangen-N=C3=BCrnberg

Prof. Kees Vuik, Delft University<= /span>