Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness.
Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness.
复制标题
池化问题中的分段参数结构：从稀疏强多项式解到 NP 难度。
DOI：
10.1007/s10898-017-0577-y
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Baltean-Lugojan R
中科院分区：
文献类型：
--
作者：
Baltean-Lugojan R
标准池问题是过程系统工程应用中常见的非凸二次约束优化问题的NP-难子类。我们采取参数化的方法来揭示拓扑结构和稀疏性，专注于单一的质量标准池问题itsp制定。这种方法揭示的结构验证了Christodoulos A. Floudas的直觉，即池化问题根源于分段定义的函数。我们引入主导的活动拓扑下放松流的可用性，明确识别池问题的稀疏性，并表明，稀疏模式的活动拓扑结构与分段目标函数。最后，本文解释了稀疏性消失的条件以及组合复杂性跨越P/NP边界的条件。我们正式提出了各种专门的单质量池问题子类所获得的结果和他们的推导。
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 itsp-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 theP/NPboundary. We formally present the results obtained and their derivations for various specialized single quality pooling problem subclasses.