Much work on heat exchanger network synthesis (HENS) via mathematical programming has employed a stagewise superstructure with the assumption of isothermal mixing. It is well known that the superstructure may miss potentially better networks. In this article, we propose a mixed-integer nonlinear programming formulation and a solution strategy to incorporate non-isothermal mixing in HENS. We use an existing modification of the stagewise superstructure, propose novel and improved temperature bounds, and propose logical constraints to obtain superior HENs. Using several examples, we show that our approach finds superior networks compared to those known in the literature, especially for larger and more difficult problems. Furthermore, we propose exact approaches for handling log-mean temperature difference (LMTD) without numerical difficulty, and compare the effectiveness of the known LMTD approximations. We also show that including the stage bypass variables and constraints improves solution quality and efficiency. (C) 2012 Elsevier Ltd. All rights reserved.