Abstract We address direct multiple shooting based algorithms for nonlinear model predictive control, with a focus on problems with long prediction horizons. We describe different efficient multiple shooting variants with a computational effort that is only linear in the horizon length. Proposed techniques comprise structure exploiting linear algebra on the one hand, and approximation of derivative information in an adjoint Sequential Quadratic Programming method on the other hand. For explicit one-step methods for ordinary differential equations we address the issue of consistent and fast generation of both forward and adjoint derivatives of dynamic process models according to the principle of Internal Numerical Differentiation. We discuss the applicability of the proposed methods at the example of three benchmark problems. These have recently been addressed in literature and serve to evaluate the relative performance of each of the proposed methods for both off-line optimal control and on-line nonlinear model predictive control. Throughout, we compare against results published for a recently proposed collocation approach based on finite elements.