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 Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness. Zbl 1405.90103Baltean-Lugojan, Radu; Misener, Ruth 2018 all top 5 Cited by 14 Authors 1 Baltean-Lugojan, Radu 1 Chen, Yifu 1 Dahl, Joachim 1 D’Ambrosio, Claudia 1 de Klerk, Etienne 1 Dey, Santanu Subhas 1 Kocuk, Burak 1 Linderoth, Jeff T. 1 Luedtke, James R. 1 Marandi, Ahmadreza 1 Maravelias, Christos T. 1 Misener, Ruth 1 Santana, Asteroide 1 Schweiger, Jonas Cited in 3 Serials 3 Journal of Global Optimization 1 Discrete Applied Mathematics 1 SIAM Journal on Optimization Cited in 2 Fields 5 Operations research, mathematical programming (90-XX) 1 Calculus of variations and optimal control; optimization (49-XX) Citations by Year