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.
Keywords for this software
References in zbMATH (referenced in 5 articles , 1 standard article )
Showing results 1 to 5 of 5.
- Chen, Yifu; Maravelias, Christos T.: Preprocessing algorithm and tightening constraints for multiperiod blend scheduling: cost minimization (2020)
- Dey, Santanu S.; Kocuk, Burak; Santana, Asteroide: Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem (2020)
- Luedtke, James; D’Ambrosio, Claudia; Linderoth, Jeff; Schweiger, Jonas: Strong convex nonlinear relaxations of the pooling problem (2020)
- Marandi, Ahmadreza; de Klerk, Etienne; Dahl, Joachim: Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy (2020)
- Baltean-Lugojan, Radu; Misener, Ruth: Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness (2018)