TR2020-152

Early Termination of Convex QP Solvers in Mixed-Integer Programming for Real-Time Decision Making


    •  Liang, J., Di Cairano, S., Quirynen, R., "Early Termination of Convex QP Solvers in Mixed-Integer Programming for Real-Time Decision Making", L-CSS with ACC 2021 Option, DOI: 10.1109/​LCSYS.2020.3038677, Vol. 5, No. 4, pp. 1417-1422, November 2020.
      BibTeX TR2020-152 PDF Video
      • @article{Liang2020nov,
      • author = {Liang, Jiaming and Di Cairano, Stefano and Quirynen, Rien},
      • title = {Early Termination of Convex QP Solvers in Mixed-Integer Programming for Real-Time Decision Making},
      • journal = {L-CSS with ACC 2021 Option},
      • year = 2020,
      • volume = 5,
      • number = 4,
      • pages = {1417--1422},
      • month = nov,
      • doi = {10.1109/LCSYS.2020.3038677},
      • url = {https://www.merl.com/publications/TR2020-152}
      • }
  • MERL Contact:
  • Research Areas:

    Control, Optimization

Abstract:

The branch-and-bound optimization algorithm for mixed-integer model predictive control (MI-MPC) solves several convex quadratic program relaxations, but often the solutions are discarded based on already known integer feasible solutions. This paper presents a projection and early termination strategy for infeasible interior point methods to reduce the computational effort of finding a globally optimal solution for MI-MPC. The method is shown to be also effective for infeasibility detection of the convex relaxations. We present numerical simulation results with a reduction of the total number of solver iterations by 42% for an MI-MPC example of decision making for automated driving with obstacle avoidance constraints.

 

  • Related News & Events

    •  NEWS    Rien Quirynen to give an invited talk at the University of California Santa Cruz
      Date: November 14, 2022
      Where: Zoom
      Research Areas: Control, Dynamical Systems, Optimization, Robotics
      Brief
      • Rien Quirynen will give an invited talk at the Electrical and Computer Engineering Department, University of California Santa Cruz on "Real-time Motion Planning and Predictive Control by Mixed-integer Programming for Autonomous Vehicles". The talk will present recent work on a tailored branch-and-bound method for real-time motion planning and decision making on embedded processing units, and recent results for two applications related to automated driving and traffic control.
    •  
  • Related Video