  Heat exchanger network synthesis exploits excess heat by integrating process
hot and cold streams and improves energy efficiency by reducing utility usage.
Determining provably good solutions to the minimum number of matches is a
bottleneck of designing a heat recovery network using the sequential method.
This subproblem is an NP-hard mixed-integer linear program exhibiting
combinatorial explosion in the possible hot and cold stream configurations. We
explore this challenging optimization problem from a graph theoretic
perspective and correlate it with other special optimization problems such as
cost flow network and packing problems. In the case of a single temperature
interval, we develop a new optimization formulation without problematic big-M
parameters. We develop heuristic methods with performance guarantees using
three approaches: (i) relaxation rounding, (ii) water filling, and (iii) greedy
packing. Numerical results from a collection of 51 instances substantiate the
strength of the methods.
