TR2019-050

A Structure Exploiting Branch-and-Bound Algorithm for Mixed-Integer Model Predictive Control


    •  Hespanhol, P., Quirynen, R., Di Cairano, S., "A Structure Exploiting Branch-and-Bound Algorithm for Mixed-Integer Model Predictive Control", European Control Conference (ECC), DOI: 10.23919/​ECC.2019.8796242, June 2019, pp. 2763-2768.
      BibTeX TR2019-050 PDF
      • @inproceedings{Hespanhol2019jun,
      • author = {Hespanhol, Pedro and Quirynen, Rien and Di Cairano, Stefano},
      • title = {A Structure Exploiting Branch-and-Bound Algorithm for Mixed-Integer Model Predictive Control},
      • booktitle = {European Control Conference (ECC)},
      • year = 2019,
      • pages = {2763--2768},
      • month = jun,
      • doi = {10.23919/ECC.2019.8796242},
      • url = {https://www.merl.com/publications/TR2019-050}
      • }
  • MERL Contact:
  • Research Areas:

    Control, Optimization

Abstract:

Mixed-integer model predictive control (MI-MPC) requires the solution of a mixed-integer quadratic program (MIQP) at each sampling instant under strict timing constraints, where part of the state and control variables can only assume a discrete set of values. Several applications in automotive, aerospace and hybrid systems are practical examples of how such discrete-valued variables arise. We utilize the sequential nature and the problem structure of MI-MPC in order to provide a branch-and-bound algorithm that can exploit not only the block-sparse optimal control structure of the problem but that can also be warm started by propagating information from branch-and-bound trees and solution paths at previous time steps. We illustrate the computational performance of the proposed algorithm and compare against current state-of-the-art solvers for a standard hybrid MPC case study, based on a preliminary implementation in MATLAB and C code.

 

  • Related News & Events

  • Related Publication

  •  Hespanhol, P., Quirynen, R., Di Cairano, S., "A Structure Exploiting Branch-and-Bound Algorithm for Mixed-Integer Model Predictive Control", arXiv, March 2019.
    BibTeX arXiv
    • @article{Hespanhol2019mar,
    • author = {Hespanhol, Pedro and Quirynen, Rien and Di Cairano, Stefano},
    • title = {A Structure Exploiting Branch-and-Bound Algorithm for Mixed-Integer Model Predictive Control},
    • journal = {arXiv},
    • year = 2019,
    • month = mar,
    • url = {https://arxiv.org/abs/1903.09117}
    • }