Current methods for the evolutionary synthesis of heat exchanger networks (HENs) using the concepts of paths and loops, do not guarantee optimality nor do they address the issue of the feasibility of an evolutionary modification step. In this work, an optimization problem formulation for the evolutionary synthesis of HEN is proposed. The principal advantage of using this approach is that it provides information on whether a specified evolutionary step (such as deletion of an existing exchanger) is feasible or not. Furthermore, it is useful in determining the optimal solution corresponding to each evolutionary step. A process graph representation of a HEN is proposed for formulating the optimization problem. This representation unifies the traditional concept of paths and loops and allows any evolutionary step to be accomplished by circulating appropriate enthalpy flows around a set of independent cycles of the HEN process graph. By exploiting this feature, a tight optimization problem is formulated for any evolutionary step. The efficacy of the proposed approach is demonstrated through examples both for energy as well as for total cost minimization. The proposed approach can be integrated with PDM methods, because it fits well with the PDM philosophy of allowing the design engineer to retain control while providing feedback on the best possible solution achievable corresponding to any evolutionary design modification chosen by the designer.