The chemical process industry is a major user of energy. Energy recovery via heat integration is a long established practice in this industry. The existing mathematical programming based approaches for simultaneous heat exchanger network synthesis (HENS) have employed two superstructures (Floudas et al., 1986. AlChE J. 32, 276-290; Yee and Grossmann, 1990. Comput. Chem. Eng. 14, 1165-1184) with well-documented limitations. We propose two new superstructures and corresponding mixed integer nonlinear programming (MINLP) models for simultaneous HENS. While one superstructure is multistage, match-centric, and combines the strengths of existing superstructures, the other has no stages, is exchanger-centric, and is entirely distinct. Both superstructures allow cross flows, cyclic matching, series matches on a substream, multiple utilities, and utility placement at any stage. They admit several network configurations that the existing superstructures do not. We also present novel ways of modeling temperature changes and approaches. We demonstrate significant advantages of our first model by obtaining networks with lower total annualized costs than those reported for seven literature examples. The second model, however, requires further work to improve computational efficiency. While our work improves the quality of HENS solutions, solution speed and global optimality are challenges that need further work. (C) 2013 Elsevier Ltd. All rights reserved.