Warm Start of Mixed-Integer Programs for Model Predictive Control of Hybrid Systems
- 7 July 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 66 (6) , 2433-2448
Abstract
In hybrid Model Predictive Control (MPC), a Mixed-Integer Quadratic Program (MIQP) is solved at each sampling time to compute the optimal control action. Although these optimizations are generally very demanding, in MPC we expect consecutive problem instances to be nearly identical. This paper addresses the question of how computations performed at one time step can be reused to accelerate (warm start) the solution of subsequent MIQPs. Reoptimization is not a rare practice in integer programming: for small variations of certain problem data, the branch-and-bound algorithm allows an efficient reuse of its search tree and the dual bounds of its leaf nodes. In this paper we extend these ideas to the receding-horizon settings of MPC. The warm-start algorithm we propose copes naturally with arbitrary model errors, has a negligible computational cost, and frequently enables an a-priori pruning of most of the search space. Theoretical considerations and experimental evidence show that the proposed method tends to reduce the combinatorial complexity of the hybrid MPC problem to that of a one-step look-ahead optimization, greatly easing the online computation burden.Keywords
All Related Versions
Funding Information
- Grass Instruments Company
- Office of Naval Research (N00014-18-1-2210)
This publication has 54 references indexed in Scilit:
- Stable dynamic walking over uneven terrainThe International Journal of Robotics Research, 2011
- An online active set strategy to overcome the limitations of explicit MPCInternational Journal of Robust and Nonlinear Control, 2007
- Robust variable horizon model predictive control for vehicle maneuveringInternational Journal of Robust and Nonlinear Control, 2006
- Dynamic programming for constrained optimal control of discrete-time linear hybrid systemsAutomatica, 2005
- The explicit linear quadratic regulator for constrained systemsAutomatica, 2002
- Constrained model predictive control: Stability and optimalityAutomatica, 2000
- Control of systems integrating logic, dynamics, and constraintsAutomatica, 1999
- Min-max feedback model predictive control for constrained linear systemsIEEE Transactions on Automatic Control, 1998
- Robust receding horizon control of constrained nonlinear systemsIEEE Transactions on Automatic Control, 1993
- Linear systems with state and control constraints: the theory and application of maximal output admissible setsIEEE Transactions on Automatic Control, 1991