A methodology was developed for the automated design and synthesis of heat exchanger networks (HEN) when the thermal properties of streams vary significantly with temperature. The optimization approach of Rodriguez (2005) was extended by including a non-linear solver that converts the infeasible heat exchanger network designs (generated by the SA algorithm) to feasible ones: the exchanger duties were reallocated within the whole network, where the structure of the HEN was fixed. When evaluating alternative HEN designs, re-piping and re-sequencing of existing exchangers were tracked and costed with reference to the exiting HEN structure. To facilitate the generation of reachable solutions, the number of modifications to an existing HEN can be constrained. The application of the approach for the retrofit design and analysis of an existing preheat train for a crude oil distillation column was presented. This is an abstract of a paper presented at the AIChE Spring National Meeting (New Orleans, LA 4/6-10/2008).