On mixed-integer optimal control with constrained total variation of the integer control
- PDF / 3,468,025 Bytes
- 49 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 199 Views
On mixed‑integer optimal control with constrained total variation of the integer control Sebastian Sager1 · Clemens Zeile1 Received: 21 October 2019 / Accepted: 5 November 2020 © The Author(s) 2020
Abstract The combinatorial integral approximation (CIA) decomposition suggests solving mixed-integer optimal control problems by solving one continuous nonlinear control problem and one mixed-integer linear program (MILP). Unrealistic frequent switching can be avoided by adding a constraint on the total variation to the MILP. Within this work, we present a fast heuristic way to solve this CIA problem and investigate in which situations optimality of the constructed feasible solution is guaranteed. In the second part of this article, we show tight bounds on the integrality gap between a relaxed continuous control trajectory and an integer feasible one in the case of two controls. Finally, we present numerical experiments to highlight the proposed algorithm’s advantages in terms of run time and solution quality. Keywords Mixed-integer linear programming · Optimal control · Discrete approximations · Switched dynamic systems · Approximation methods and heuristics Mathematics Subject Classification 49M20 · 49M27 · 90B35 · 90C11 · 90C59
1 Introduction Mixed-Integer Optimal Control has been established as a useful tool for modeling real-world problems [6, 10, 22, 33]. In practice, only an optimal control policy is realistic that avoids frequent switching between the system modes. However, it remains an open research question as to how switching costs or a limited number of switches can be efficiently incorporated into the optimization problem. * Clemens Zeile [email protected] Sebastian Sager [email protected] 1
Department of Mathematics, Otto-von-Guericke-Universität Magdeburg, Magdeburg 39106, Germany
13
Vol.:(0123456789)
S. Sager, C. Zeile
In this article, we follow a first-discretize-then-optimize approach because in contrast to indirect methods and dynamic programming, a more generic problem class can be solved for which efficient numerical methods, in particular, a decomposition approach used in this article, are available. By this approach, the control problem is discretized via, e.g., Direct Multiple Shooting [5] or Direct Collocation [29], which leads to a mixed-integer nonlinear program (MINLP). This problem class is NPhard in general, so that it has been proposed to reduce complexity by solving first the relaxed problem with dropped integrality constraint, which is a nonlinear program (NLP), before approximating relaxed controls in a second step with binary controls as part of a mixed-integer linear program (MILP). The second problem is usually referred to as combinatorial integral approximation (CIA) problem [27], whereas the whole algorithm is called CIA decomposition [31]. It is common to use the fast Sum-Up Rounding (SUR) heuristic [24] to find a feasible approximative solution for the CIA problem, so that this second step is also named rounding. However, standard SUR does not consider time-coup
Data Loading...
