A Mixed-Integer Nonlinear Problem Algorithm to Control Finite State Machines Using Branch and Bound

The dynamics of a large variety of systems such as micro-grids and parallel hybrid cars can be described using finite state machines. The optimal control of these sys- tems leads to mixed-integer non-linear programming (MINLP) problems. This class of problems typically belongs to the non-deterministic polynomial-time hard problems since they combine both the computational intensity of solving problems with discrete variables and the complexity of solving non- linear functions. In the last decade, different techniques are developed to reach a global optimal solution for convex MINLP problems, such as branch & bound, outer approximation or the generalized benders decomposition algorithm. These techniques often have difficulties in efficiently handling the constraints of state machines. These constraints include the minimum time to stay within a state or the minimum cycle time before the same state can be reached again. In order to tackle these issues, the paper proposes a new technique that exploits the properties of a state machine within the branch & bound tree to reduce execution time. This reduction is achieved by separately solving the state machine variables and relaxing the switches between states using sigmoid functions. As a result, the technique reduces the number of explored nodes in the branch & bound tree significantly. The algorithm can be used in an online optimization strategy when employing a model predictive control framework that preserves added constraints from a previous iteration in the next iteration. A numerical simulation demonstrates the computational efficiency of this algorithm.

ISBN:978-1-6654-0782-3

Jaar van publicatie:2021

Toegankelijkheid:Closed