Improved complexity analysis of branch and bound for hybrid MPC

In this work, the computational effort of Mixed Integer Quadratic Programming solvers based on branch and bound is studied. The origin of this interest is that hybrid MPC problems for Mixed Logical Dynamical systems can be formulated as optimization problems in this form and since these have to be solved in real-time, it is interesting to be able to compute a good bound on the computational complexity. Classically, the bound on the worst case computational complexity is given by the case when it is necessary to expand all nodes in the entire tree. The usefulness of branch and bound relies on the fact that this worst case scenario is very rare in practice. The objective in this work is to reduce the gap between the conservative worst case bound on the number of nodes and the number of nodes actually necessary to explore on-line in the optimization routine. Approaches to compute this bound are presented and motivated theoretically and the performance of the analysis is evaluated in numerical examples.