Cargando…
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 p...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer US
2017
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6417401/ https://www.ncbi.nlm.nih.gov/pubmed/30956395 http://dx.doi.org/10.1007/s10898-017-0577-y |
_version_ | 1783403566669496320 |
---|---|
author | Baltean-Lugojan, Radu Misener, Ruth |
author_facet | Baltean-Lugojan, Radu Misener, Ruth |
author_sort | Baltean-Lugojan, Radu |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-6417401 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2017 |
publisher | Springer US |
record_format | MEDLINE/PubMed |
spelling | pubmed-64174012019-04-03 Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness Baltean-Lugojan, Radu Misener, Ruth J Glob Optim Article 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. Springer US 2017-10-25 2018 /pmc/articles/PMC6417401/ /pubmed/30956395 http://dx.doi.org/10.1007/s10898-017-0577-y Text en © The Author(s) 2017 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. |
spellingShingle | Article Baltean-Lugojan, Radu Misener, Ruth Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness |
title | Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness |
title_full | Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness |
title_fullStr | Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness |
title_full_unstemmed | Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness |
title_short | Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness |
title_sort | piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to np-hardness |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6417401/ https://www.ncbi.nlm.nih.gov/pubmed/30956395 http://dx.doi.org/10.1007/s10898-017-0577-y |
work_keys_str_mv | AT balteanlugojanradu piecewiseparametricstructureinthepoolingproblemfromsparsestronglypolynomialsolutionstonphardness AT misenerruth piecewiseparametricstructureinthepoolingproblemfromsparsestronglypolynomialsolutionstonphardness |