This paper presents an efficient optimization algorithm suitable for online solution of mixed integer nonlinear programs resulting from the model predictive control (MPC) of nonlinear hybrid systems. The system model is based on a recently proposed multiple partially linear (MPL) modeling scheme. The algorithm, based on generalized outer approximation (GOA), uses structural information of the canonical MPL framework as well as analytical expressions for the objective function and constraints of a relatively simple primal problem as well as the master problem. Specifically, the primal problem of GOA reduces to a quadratic program when MPL models are used in MPC. Computational efficiency of the algorithm over the branch and bound strategy is demonstrated using a simulated benchmark three-spherical tank system and a hydraulic process plant.