Mathematical programming using superstructure formulations has been used for cost efficient heat exchanger network synthesis (HENS) for about three decades now and significant improvements have been achieved since then. One major problem is the combinatorial nature of the underlying superstructure formulations which means that the mathematical complexity of the HENS problem scales exponentially with problem size. In this paper a novel approach using convex linear approximations is presented for simultaneous HENS. The linearization is carried out prior to optimization and the original Mixed Integer Non-Linear Programming (MINLP) problem is reformulated into a Mixed Integer Linear Programming (MILP) problem. For the linearized problem a global optimum can be obtained much faster compared to the original MINLP formulation. For all presented case-studies feasible solutions could be obtained, which compare well with results from other authors. (c) 2018 Elsevier Ltd. All rights reserved.