Heat exchanger network synthesis (HENS) has been the subject of a significa
nt amount of research over the last 40 years. While significant progress ha
s been made towards solving the problem, its computational complexity is no
t known, i.e., it is not known whether a polynomial algorithm might exist f
or the problem or not. This issue is addressed in this paper through a comp
utational complexity analysis.
We prove that HENS is, NP-hard, thus refuting the possibility for the exist
ence of a computationally efficient (polynomial) exact solution algorithm f
or this problem. While this complexity characterization may not be surprisi
ng, our analysis shows that HENS is NP-hard in the strong sense. Therefore,
HENS belongs to a particularly difficult class of hard optimization proble
ms. Further, via restriction to the 3-partition problem, our complexity pro
ofs 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 coefficie
nts, and uniform heat requirements of all cold streams.
These results facilitate the computational complexity analysis of more comp
lex HENS problems and provide new insights to structural properties of the
problem. They also provide motivation for the development of specialized op
timization algorithms and approximation schemes. (C) 2001 Elsevier Science
Ltd. All rights reserved.