Pooling Problems with Single-Flow Constraints

Abstract

The pooling problem is a frequently studied extension of the traditional minimum cost flow problem, in which the composition of the flow is subject to restrictions. In a network consisting of three layers of nodes, the composition is given at the source layer. In the intermediate nodes, referred to as pools, the composition is a weighted average of the compositions in entering flow streams. The same is true at the sink layer, where upper bounds on the concentration of each component apply. Motivated by practical applications, and needs for heuristic methods for the standard pooling problem, the current work focuses on pooling problems where the flow graph is restricted to satisfy certain sparsity conditions. We consider in particular the requirements that each pool receives flow from at most one neighboring source, or sends flow to at most one neighboring sink. We prove that the pooling problem remains NP-hard after this and other similar extensions. It is also demonstrated how the single-flow constrained extensions can be modeled by means of mixed integer linear programming (MILP), without introducing bilinear terms. We also show that such MILP-models are useful for computing good feasible solutions to the original problem.