(300d) Heuristics with Performance Guarantees for the Minimum Number of Matches in Heat Recovery Networks

Misener, R., Imperial College
Kouyialis, G., Imperial College London
Optimal heat exchanger network synthesis improves heat recovery in chemical processes [1, 2, 3, 4]. Heat exchanger network synthesis is a nonconvex mixed-integer nonlinear optimization problem that may be solved simultaneously, i.e. to generate an optimal network without decomposition [5, 6, 7, 8]. An alternative, sequential method, decomposes the synthesis problem into: (i) minimizing utility cost, (ii) minimizing the number of matches, (iii) deriving many possible superstructures, (iv) minimizing the investment cost, and (v) configuring the final network [9]. The sequential method cannot guarantee global optimality of the original problem, but it reduces the computational burden.

We investigate the minimum number of matches subproblem of the sequential method. This subproblem is an NP–hard mixed-integer linear program (MILP) exhibiting: combinatorial explosion in the possible hot and cold stream configurations and symmetric mathematical structure creating unnecessarily large search trees [10, 11, 12]. Because the minimum number of matches subproblem still poses computational difficulty for moderately-sized networks [13], we develop provably efficient approximation algorithms with guaranteed solution quality and run-time bounds.

Previous work achieves a 2-approximation ratio for a single temperature interval and a non-constant approximation ratio for multiple temperature intervals scaling with the number of hot and cold streams [14]. This presentation develops new approximation algorithms with improved performance guarantees and proves their tightness. In the sequential method, many possible stream configurations are required to evaluate the minimum overall cost. So a complementary contribution of this presentation is developing (provably) efficient algorithms producing multiple solutions. The proposed algorithms and novel MILP formulations are validated experimentally.

We close the presentation by reflecting on the tremendous contribution of Professor Christodoulos A. Floudas to both the algorithmic methodology and practical application of process systems engineering. We show that Professor Floudas' legacy, which is integral to this current work, also offers a fruitful path to the future of multiscale systems engineering.

  1. C.A. Floudas and I.E. Grossmann. Synthesis of flexible heat exchanger networks with uncertain flowrates and temperatures. Comput Chem Eng, 11(4):319–336, 1987.
  2. J. A. Elia, R. C. Baliban, and C. A. Floudas. Toward novel hybrid biomass, coal, and natural gas processes for satisfying current transportation fuel demands, 2: Simultaneous heat and power integration. Ind Eng Chem Res, 49(16):7371–7388, 2010.
  3. R. C. Baliban, J. A. Elia, R. Misener, and C. A. Floudas. Global optimization of a MINLP process synthesis model for thermochemical based conversion of hybrid coal, biomass, and natural gas to liquid fuels. Comput Chem Eng, 42:64–86, 2012.
  4. M. Escobar and J. O. Trierweiler. Optimal heat exchanger network synthesis: A case study comparison. Appl Therm Eng, 51(1-2):801–826, 2013.
  5. T. F. Yee and I. E. Grossmann. Simultaneous optimization models for heat integration – II. Heat exchanger network synthesis. Comput Chem Eng, 14(10):1165–1184, 1990.
  6. A. R. Ciric and C. A. Floudas. Heat exchanger network synthesis without decomposition. Comput Chem Eng, 15(6):385–396, 1991.
  7. K. P. Papalexandri and E. N. Pistikopoulos. Synthesis and retrofit design of operable heat exchanger networks. 1. Flexibility and structural controllability aspects. Ind Eng Chem Res, 33(7):1718–1737, 1994.
  8. M. Mistry and R. Misener. Optimising heat exchanger network synthesis using convexity properties of the logarithmic mean temperature difference. Comput Chem Eng, 94:1–17, 2016.
  9. C. A. Floudas, A. R. Ciric, and I. E. Grossmann. Automatic synthesis of optimum heat exchanger network configurations. AIChE J, 32(2):276–290, 1986.
  10. K. C. Furman and N. V. Sahinidis. Computational complexity of heat exchanger network synthesis. Comput Chem Eng, 25:1371 – 1390, 2001.
  11. C. A. Floudas. Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications Topics in Chemical Engineering. Topics in Chemical Engineering. Oxford University Press, New York, 1995.
  12. G. Kouyialis and R. Misener. Detecting symmetry in designing heat exchanger networks. In C. Maravelias, J. Wassick, E. Ydstie, and L. Megan, editors, Proceedings of Foundations of Computer Aided Process Operations / Chemical Process Control, 2017.
  13. Y. Chen, I. E. Grossmann, and D. C. Miller. Computational strategies for large-scale MILP transshipment models for heat exchanger network synthesis. Comput Chem Eng, 82:68–83, 2015.
  14. K. C. Furman and N. V. Sahinidis. Approximation Algorithms for the Minimum Number of Matches Problem in Heat Exchanger Network Synthesis. Ind Eng Chem Res, 43(14):3554– 3565, 2004.