Determining the minimum number of units is an important step in heat exchanger network synthesis (HENS). The MILP transshipment model (Papoulias and Grossmann, 1983) and transportation model (Cerda and Westerberg, 1983) were developed for this purpose. However, they are computationally expensive when solving for large-scale problems. Several approaches are studied in this paper to enable the fast solution of large-scale MILP transshipment models. Model reformulation techniques are developed for tighter formulations with reduced LP relaxation gaps. Solution strategies are also proposed for improving the efficiency of the branch and bound method. Both approaches aim at finding the exact global optimal solution with reduced solution times. Several approximation approaches are also developed for finding good approximate solutions in relatively short times. Case study results show that the MILP transshipment model can be solved for relatively large-scale problems in reasonable times by applying the approaches proposed in this paper. (C) 2015 Published by Elsevier Ltd.