Improved rank-one-based relaxations and bound tightening techniques for the pooling problem

Official URL: https://dx.doi.org/10.1007/s11081-025-09997-6

The pooling problem is a classical NP-hard problem in the chemical process and petroleum industries. This problem is modeled as a nonlinear, nonconvex network flow problem in which raw materials with different specifications are blended in some intermediate tanks and mixed again to obtain the final products with the desired specifications. The analysis of the pooling problem is quite an active research area, and different exact formulations, relaxations, and restrictions are proposed. In this paper, we focus on a recently proposed rank-one-based formulation of the pooling problem. In particular, we study a recurring substructure in this formulation defined by the set of nonnegative, rank-one matrices with bounded row sums, column sums, and the overall sum. We show that the convex hull of this set is second-order cone representable. In addition, we propose an improved compact-size polyhedral outer-approximation and families of valid inequalities for this set. To further strengthen these convexification approaches, we develop two bound tightening techniques that refine the capacities of source, pool, and terminal nodes, as well as flow bounds on arcs. One is a simple, rule-based approach using network structure (e.g., supply, demand, and neighboring capacities), while the other solves auxiliary optimization problems to compute tighter bounds. Our computational experiments show that the newly proposed polyhedral outer-approximation can improve upon the traditional linear programming relaxations of the pooling problem in terms of the dual bound. Furthermore, bound tightening techniques reduce the computational time spent on both the exact method, linear programming, and mixed-integer linear programming relaxations.