Mixed-integer dynamic optimization (MIDO) problems arise in chemical engineering whenever discrete and continuous decisions are to be made for a system described by a transient model. Areas of application include integrated design and control, synthesis of reactor networks, reduction of kinetic mechanisms and optimization of hybrid systems. This article presents new formulations and algorithms for solving MIDO problems. The algorithms are based on decomposition into primal, dynamic optimization and master, mixed-integer linear programming sub-problems. They do not depend on the use of a particular primal dynamic optimization method and they do not require the solution of an intermediate adjoint problem for constructing the master problem, even when the integer variables appear explicitly in the differential-algebraic equation system. The practical potential of the algorithms is demonstrated with two distillation design and control optimization examples.