This article presents an algorithm for the exact solution of explicit hybrid model-predictive control problems of time-invariant, discrete-time mixed logical dynamical systems. Using multiparametric programming, this control problem is formulated as a multiparametric mixed-integer quadratic programming problem where the initial states of the system are treated as parameters. In conjunction with decomposition type or branch-and-bound type approaches, the proposed solution strategy first creates affine relaxations of nonconvex critical regions that result from the comparison of two quadratic objective functions. These relaxations are then used to generate an affine outer approximation for the critical regions. Upon termination, the bounded space of the initial states is partitioned into possibly nonconvex critical regions and corresponding optimal control laws. (C) 2015 Elsevier Ltd. All rights reserved.