liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Improved complexity analysis of branch and bound for hybrid MPC
Automatic Control Laboratory, ETH Zürich, CH-8092, Switzerland .ORCID iD: 0000-0001-6957-2603
Automatic Control Laboratory, ETH Zürich, CH-8092, Switzerland .
2010 (English)In: Proceedings of the 49th IEEE Conference on Decision and Control (CDC), 2010, 4216-4222 p.Conference paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2010. 4216-4222 p.
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:liu:diva-129289DOI: 10.1109/CDC.2010.5717242ISBN: 978-1-4244-7746-3OAI: oai:DiVA.org:liu-129289DiVA: diva2:937540
Conference
49th IEEE Conference on Decision and Control (CDC), 15-17 December 2010, Atlanta, GA
Available from: 2016-06-15 Created: 2016-06-15 Last updated: 2016-06-29

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Axehill, Daniel
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 14 hits
ReferencesLink to record
Permanent link

Direct link