Distillation is the most important separation technique even for nonideal and azeotropic mixtures. A methodology for the synthesis of superstructures for the structural optimization of such distillation processes by means of mixed integer nonlinear programming (MINLP) is presented. The superstructure is derived knowing the phase equilibrium and the feed composition. The basic idea is the description of the distillation columns under minimum reflux conditions by the model of the preferred separation. Each column is supposed to perform a nonsharp split at minimum reflux (preferred split). Thus, an upper bound on the number of columns can be determined. The column interconnections allow for direct heat integration and recycling of intermediate products. This ensures that even complex process alternatives are included in the superstructure. The methodology is applicable to zeotropic and homogeneous azeotropic mixtures with at least three components. Examples for the separation of a ternary mixture with a minimum azeotrope and a distillation boundary are given.