TY - JOUR
T1 - Computational complexity of heat exchanger network synthesis
AU - Furman, Kevin C.
AU - Sahinidis, Nikolaos V.
N1 - Funding Information:
The authors wish to thank Dr. Udatta Palekar and Dr. Shabbir Ahmed for helpful comments and suggestions. The authors are also grateful to Dr. William R. Johns whose comments motivated us to improve the presentation so as to make the paper more accessible to the audience. Partial financial support from the National Science Foundation under grant CTS-9704643 is gratefully acknowledged.
PY - 2001/9/15
Y1 - 2001/9/15
N2 - Heat exchanger network synthesis (HENS) has been the subject of a significant amount of research over the last 40 years. While significant progress has been made towards solving the problem, its computational complexity is not known, i.e., it is not known whether a polynomial algorithm might exist for the problem or not. This issue is addressed in this paper through a computational complexity analysis. We prove that HENS is NP-hard, thus refuting the possibility for the existence of a computationally efficient (polynomial) exact solution algorithm for this problem. While this complexity characterization may not be surprising, our analysis shows that HENS is NP-hard in the strong sense. Therefore, HENS belongs to a particularly difficult class of hard optimization problems. Further, via restriction to the 3-partition problem, our complexity proofs reveal that even the following simple HENS subproblems are NP-hard in the strong sense: (a) the minimum number of matches target problem, (b) the matches problem with only one temperature interval, uniform cost coefficients, and uniform heat requirements of all cold streams. These results facilitate the computational complexity analysis of more complex HENS problems and provide new insights to structural properties of the problem. They also provide motivation for the development of specialized optimization algorithms and approximation schemes.
AB - Heat exchanger network synthesis (HENS) has been the subject of a significant amount of research over the last 40 years. While significant progress has been made towards solving the problem, its computational complexity is not known, i.e., it is not known whether a polynomial algorithm might exist for the problem or not. This issue is addressed in this paper through a computational complexity analysis. We prove that HENS is NP-hard, thus refuting the possibility for the existence of a computationally efficient (polynomial) exact solution algorithm for this problem. While this complexity characterization may not be surprising, our analysis shows that HENS is NP-hard in the strong sense. Therefore, HENS belongs to a particularly difficult class of hard optimization problems. Further, via restriction to the 3-partition problem, our complexity proofs reveal that even the following simple HENS subproblems are NP-hard in the strong sense: (a) the minimum number of matches target problem, (b) the matches problem with only one temperature interval, uniform cost coefficients, and uniform heat requirements of all cold streams. These results facilitate the computational complexity analysis of more complex HENS problems and provide new insights to structural properties of the problem. They also provide motivation for the development of specialized optimization algorithms and approximation schemes.
KW - Computational complexity
KW - Heat exchanger network synthesis
KW - Optimization algorithms
UR - http://www.scopus.com/inward/record.url?scp=0035884467&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0035884467&partnerID=8YFLogxK
U2 - 10.1016/S0098-1354(01)00681-0
DO - 10.1016/S0098-1354(01)00681-0
M3 - Article
AN - SCOPUS:0035884467
SN - 0098-1354
VL - 25
SP - 1371
EP - 1390
JO - Computers and Chemical Engineering
JF - Computers and Chemical Engineering
IS - 9-10
ER -