Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Improved Complexity Analysis of Branch and Bound for Hybrid MPC


D. Axehill, M. Morari

IEEE Conference on Decision and Control, Atlanta, USA, pp. 4216-4222

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.


Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@InProceedings { AxeMor:2010:IFA_3686,
    author={D. Axehill and M. Morari},
    title={{Improved Complexity Analysis of Branch and Bound for Hybrid
    booktitle={IEEE Conference on Decision and Control},
    address={Atlanta, USA},
Permanent link