Tailored presolve techniques in branch‐and‐bound method for fast mixed‐integer optimal control applications
Optimal Control Applications and Methods · 2023-11 · 44 (6) · 3139-3167
DOI: 10.1002/oca.3030 ↗Kurz gefasst
Fachartikel in der Zeitschrift Optimal Control Applications and Methods, online erschienen am 27.06.2023. Verfasst von Rien Quirynen und 1 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 58 Literaturangaben.
Abstract (Originalsprache)
Mixed‐integer model predictive control (MI‐MPC) can be a powerful tool for controlling hybrid systems. In case of a linear‐quadratic objective in combination with linear or piecewise‐linear system dynamics and inequality constraints, MI‐MPC needs to solve a mixed‐integer quadratic program (MIQP) at each sampling time step. This paper presents a collection of exact block‐sparse presolve techniques to efficiently remove decision variables, and to remove or tighten inequality constraints, tailored to mixed‐integer optimal control problems. In addition, we describe a novel approach based on a heuristic presolve algorithm to compute a feasible but possibly suboptimal MIQP solution. We present benchmarking results for a C code implementation of the proposed BB‐ASIPM solver, including a branch‐and‐bound (B&B) method with the proposed tailored presolve techniques and an active‐set based interior point method (ASIPM), compared against multiple state‐of‐the‐art MIQP solvers on a case study of motion planning with obstacle avoidance constraints. Finally, we demonstrate the feasibility and computational performance of the BB‐ASIPM solver in embedded system on a dSPACE Scalexio real‐time rapid prototyping unit for a second case study of stabilization for an underactuated cart‐pole with soft contacts.
Zitieren
APA
Quirynen, R., & Cairano, S. D. (2023). Tailored presolve techniques in branch‐and‐bound method for fast mixed‐integer optimal control applications. Optimal Control Applications and Methods, 44(6), 3139-3167. https://doi.org/10.1002/oca.3030
Vancouver
Quirynen R, Cairano SD. Tailored presolve techniques in branch‐and‐bound method for fast mixed‐integer optimal control applications. Optimal Control Applications and Methods. 2023;44(6):3139-3167. doi:10.1002/oca.3030
BibTeX
@article{Quirynen2023,
author = {Quirynen, Rien and Cairano, Stefano Di},
title = {Tailored presolve techniques in branch‐and‐bound method for fast mixed‐integer optimal control applications},
journal = {Optimal Control Applications and Methods},
year = {2023},
volume = {44},
number = {6},
pages = {3139--3167},
doi = {10.1002/oca.3030}
}
EUVIMED