×

StdPooling-PolyAlgos

swMATH ID: 34823
Software Authors: Baltean-Lugojan, Radu; Misener, Ruth
Description: StdPooling-PolyAlgos: Implementation of polynomial-time algorithms for subclasses of single quality standard pooling problems. Paper: Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness. The standard pooling problem is a NP-hard subclass of non-convex quadratically-constrained optimization problems that commonly arises in process systems engineering applications. We take a parametric approach to uncovering topological structure and sparsity, focusing on the single quality standard pooling problem in its (p)-formulation. The structure uncovered in this approach validates Professor Christodoulos A. Floudas’ intuition that pooling problems are rooted in piecewise-defined functions. We introduce dominant active topologies under relaxed flow availability to explicitly identify pooling problem sparsity and show that the sparse patterns of active topological structure are associated with a piecewise objective function. Finally, the paper explains the conditions under which sparsity vanishes and where the combinatorial complexity emerges to cross over the (P/NP) boundary. We formally present the results obtained and their derivations for various specialized single quality pooling problem subclasses.
Homepage: https://link.springer.com/article/10.1007/s10898-017-0577-y
Source Code: https://github.com/cog-imperial/StdPooling-PolyAlgos
Keywords: standard pooling problem; global optimization; piecewise structure; sparsity; discretization; (P/ NP) boundary; strongly-polynomial algorithms
Related Software: APOGEE; GloMIQO; GAMS Model; SPOTless; Sparse-BSOS; AIMMS; Mosek; CONOPT; BARON; GitHub; ANTIGONE; SCIP
Cited in: 5 Publications

Citations by Year