Piecewise Parametric Structure in the Pooling Problem - from Sparse Strongly-Polynomial Solutions to NP-Hardness

Radu Baltean-Lugojan, Ruth Misener

Standard pooling is a NP-hard non-convex quadratically-constrained optimization problem sub-class prevalent in large-scale process systems engineering, mired by significant optimality gaps and impractical convergence times. Via a parametric approach and sparse dominating network topologies, we formally validate the late Prof. Floudas' intuition that pooling problems are rooted in piecewise functions and justify linear approximations via sparsity from Beale et al. [1965]. A P/NP boundary linked to sparsity-vanishing conditions is delineated as a result, inspiring new approximation algorithms.