The simultaneous heat exchanger network (HEN) synthesis problem is generally formulated as a mixed integer non-linear programming (MINLP) problem by using superstructures, which embed several possible stream matches and various alternative HEN designs. The superstructures proposed by Yee et al. [1] and by Floudas et al. [2] are used for this purpose. In the present work, the graph theoretic principles used by Shivakumar and Narasimhan [3] to develop an efficient nonlinear program (NLP) formulation for Yee superstructure has been extended to the Floudas superstructure. A comparison of the NLP formulations based on the two superstructures, in terms of efficiency, scalability, convergence and quality of solution has been carried out using several test problems available in the literature. It has been shown that the Floudas superstructure is superior in terms of these performance metrics, and appears to be the best suited for optimisation based HEN synthesis. © 2010 Indian Institute of Chemical Engineers.