Accelerating linear model predictive control by constraint removal

Model predictive control (MPC) is computationally expensive, because it is based on solving an optimal control problem in every time step. We show how to reduce the computational cost of linear discrete-time MPC by detecting and removing inactive constraints from the optimal control problem. State of the art MPC implementations detect constraints that are inactive for all times and all initial conditions and remove these from the underlying optimization problem. Our approach, in contrast, detects constraints that become inactive as a function of time. More specifically, we show how to find a bound σi for each constraint i, such that a Lyapunov function value below σi implies constraint i is inactive. Since the bounds σi are independent of states and inputs, they can be determined offline. The proposed approach is easy to implement, requires simple and affordable preparatory calculations, and it does not depend on the details of the underlying optimization algorithm. We apply it to two sample MPC problems of different size. The computational cost can be reduced considerably in both cases.