The computational complexity of the pooling problem

The pooling problem is an extension of the minimum cost flow problem defined on a directed graph with three layers of nodes, where quality constraints are introduced at each terminal node. Flow entering the network at the source nodes has a given quality, at the internal nodes (pools) the entering flow is blended, and then sent to the terminal nodes where all entering flow streams are blended again. The resulting flow quality at the terminals has to satisfy given bounds. The objective is to find a cost-minimizing flow assignment that satisfies network capacities and the terminals’ quality specifications. Recently, it was proved that the pooling problem is NP-hard, and that the hardness persists when the network has a unique pool. In contrast, instances with only one source or only one terminal can be formulated as compact linear programs, and thereby solved in polynomial time. In this work, it is proved that the pooling problem remains NP-hard even if there is only one quality constraint at each terminal. Further, it is proved that the NP-hardness also persists if the number of sources and the number of terminals are no more than two, and it is proved that the problem remains hard if all in-degrees or all out-degrees are at most two. Examples of special cases in which the problem is solvable by linear programming are also given. Finally, some open problems, which need to be addressed in order to identify more closely the borderlines between polynomially solvable and NP-hard variants of the pooling problem, are pointed out.