This paper addresses the application of stochastic optimization approaches to the synthesis of heat integrated complex distillation system, which is characterized by large-scale combinatorial feature. Conventional and complex columns, thermally coupled (linked) side strippers and side rectifiers as well as heat integration between the different columns are simultaneously considered. The problem is formulated as an MINLP (mixed-integer nonlinear programming) problem. A simulated annealing algorithm is proposed to deal with the MINLP problem and a shortcut method is applied to evaluate all required design parameters as well as the total cost function. Two illustrating examples are presented.