Piecewise Parametric Structure in the Pooling Problem - from Sparse Strongly-Polynomial Solutions to NP-Hardness
Radu Baltean-Lugojan (rb2309imperial.ac.uk)
Abstract: The standard pooling problem is a NP-hard sub-class 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 of the 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 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 pooling problem instances.
Keywords: Standard pooling problem, Global optimization, Piecewise structure, Sparsity, Discretization, P/NP boundary, Strongly-polynomial algorithms
Category 1: Combinatorial Optimization
Category 2: Nonlinear Optimization (Quadratic Programming )
Citation: Working paper.
Entry Submitted: 05/22/2016
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|