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
      • @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 Contacts:
  • 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.