Explicit piecewise linear (PWL) state feedback laws solving constrained linear model predictive control (MPC) problems can be obtained by solving multi-parametric quadratic programs (mp-QP)where the parameters are the elements of the state vector. This allows MPC to be implemented via a PWL function evaluation without real-time optimization. The main drawback of this approach is dramatic increase in the number of regions in the state space partition as the number of states, inputs and constraints increases. Here we study two approaches to complexity reduction. First, we consider input trajectory parameterization which significantly reduces the number of regions. Second, we develop a search tree that allows PWL function evaluation to be implemented in real time with low computational complexity.