Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness

Radu Baltean-Lugojan () and Ruth Misener ()
Additional contact information
Radu Baltean-Lugojan: Imperial College London
Ruth Misener: Imperial College London

Journal of Global Optimization, 2018, vol. 71, issue 4, No 2, 655-690

Abstract: Abstract 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: Standard pooling problem; Global optimization; Piecewise structure; Sparsity; Discretization; P / NP boundary; Strongly-polynomial algorithms (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-017-0577-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:71:y:2018:i:4:d:10.1007_s10898-017-0577-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-017-0577-y

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().