In a heterogeneous parallel structure, two types of algorithms, Quesada Grossmann's (QG) algorithm and Tabu search (TS), are used to solve mixed integer nonlinear programming (MINLP) simultaneously. Communication is well designed between two threads running the two algorithms individually by exchanging three kinds of information during iterations. First, the best feasible solution in TS can become a valid upper bound for QG. Second, new linearization which can further tighten the lower bound of QG can be generated at the node provided by the TS. Third, additional integer variables can be fixed in QG, thus reducing the search space of TS. Numerical results show that good performance can be achieved by using the proposed method. Further analysis reveals that the heterogeneous method has the potential for superlinear speedup, which may surpass that of the traditional homogeneous parallel method for solving MINLPs. (c) 2013 Elsevier Ltd. All rights reserved.