Approximation Algorithms for the Minimum Number of Matches Problem in Heat Exchanger Network Synthesis
详细信息 查看全文
- 作者：Kevin C. Furman and Nikolaos V. Sahinidis
- 刊名：Industrial & Engineering Chemistry Research
- 出版年：2004
- 出版时间：July 7, 2004
- 年：2004
- 卷：43
- 期：14
- 页码：3554 - 3565
- 全文大小：162K
- 年卷期：v.43,no.14(July 7, 2004)
- ISSN：1520-5045
文摘
Although the use of heuristics has been prevalent in the process synthesis literature, theirjustification has been exclusively based on empirical evidence obtained through computationaltesting. As a result, heuristics currently in use offer no guarantee of optimality. Optimizationalgorithms, on the other hand, offer rigor but suffer from the combinatorial explosion ofcomputational requirements necessary to produce an optimal solution. Recognizing this gapbetween heuristic and optimization approaches in process synthesis, we propose the use ofanalytical techniques in the development and assessment of heuristics. The primary purpose ofthis paper is to introduce the analysis of algorithm performance into the field of process synthesisand develop the first approximation algorithms for process synthesis. Approximation algorithmsare heuristics with guaranteed performance. In the context of the classical matches problem inheat exchanger network synthesis, we develop approximation algorithms based on primalrounding, dual rounding, Lagrangean relaxation rounding, primal-dual approximation, andgreedy approximation. We provide an analytical characterization of the worst-case behavior ofthese as well as any heuristic that may be devised for the matches problem. In computationalexperiments with a test set of 29 problems from the literature, we find that the developed suiteof algorithms performs much better than its theoretical worst-case bound and provides solutionsthat average within 25% of optimality. On the other hand, five of these test problems are beyondthe capabilities of current state-of-the-art optimization software. Finally, we pose a number ofinteresting research challenges in this area.