Two novel formulations for the optimization of heat integration of chemical processes with variable stream data and non-linear process constraints are proposed. An NLP formulation utilizes a concept ofpseudo stream temperatures and the Plus/ Minus Principles simplifies the formulation with tight constraints. The NLP model is efficiency but the use of bi-linear constraints might sometimes deteriorate the solution quality comparing to the conventional Big-M disjunctive model. To overcome this, a Multi-Mmodel is proposed that applies the same concepts as in the NLP model together with a set of Multi-M constraints. The Multi-M model significantly reduces the number of binary variables and minimizes the size of Ms for the use in the Multi-M constraints. Results show that the NLP model spends least time in solution but sometimes converges too soon at near or local optimum. The Multi-M model is the most robust and still maintains a high efficiency in solution quality and speed. For problem with non-linear process constraints, both NLP and Multi-M models perform much better than the traditional Big-M model. (C) 2014 Elsevier Ltd. All rights reserved.