Piecewise parametric structure in the pooling problem - from sparse, strongly-polynomial solutions to NP-hardness
File(s)10.1007%2Fs10898-017-0577-y.pdf (1.21 MB)
Published version
Author(s)
Baltean-Lugojan
Misener, R
Type
Journal Article
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.
Date Issued
2018-08-01
Date Acceptance
2017-10-06
Citation
Journal of Global Optimization, 2018, 71 (4), pp.655-690
ISSN
0925-5001
Publisher
Springer Verlag
Start Page
655
End Page
690
Journal / Book Title
Journal of Global Optimization
Volume
71
Issue
4
Copyright Statement
© The Author(s) 2017. This 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.
License URL
Sponsor
Royal Academy Of Engineering
Engineering & Physical Science Research Council (EPSRC)
Grant Number
10216/118
EP/P008739/1
Subjects
Science & Technology
Technology
Physical Sciences
Operations Research & Management Science
Mathematics, Applied
Mathematics
Standard pooling problem
Global optimization
Piecewise structure
Sparsity
Discretization
P/NP boundary
Strongly-polynomial algorithms
CONSTRAINED QUADRATIC PROGRAMS
GLOBAL OPTIMIZATION APPROACH
BILINEAR PROGRAMS
NONCONVEX NLPS
ALGORITHM GOP
FORMULATIONS
RELAXATIONS
SYSTEMS
TEXACO
BRANCH
0102 Applied Mathematics
0103 Numerical And Computational Mathematics
0802 Computation Theory And Mathematics
Operations Research
Publication Status
Published
Date Publish Online
2017-10-25