# Matching Algorithms and Complexity Results for Constrained Mixed-Integer Optimal Control with Switching Costs

We extend recent work on the performance of the combinatorial integral approximation decomposition approach for Mixed-Integer Optimal Control Problems (MIOCPs) in the presence of combinatorial constraints or switching costs on an equidistant grid. For the time discretized problem, we reformulate the emerging rounding problem in the decomposition approach as a matching problem on a bipartite graph and show that a feasible integral control can be obtained by computing a maximal matching. Given a relaxed solution of an MIOCP with combinatorial constraints the approach allows the computation of a control with minimal integrated control deviation $\theta$ within $\mathcal{O}(NM\sqrt{N+M\log(N+M)})$, where $M$ is the number of binary controls and $N$ denotes the number of discretized time intervals. We derive a tight bound on $\theta$ for decomposition methods in the presence of combinatorial constraints and show that the worst-case approximation bound for this problem class is larger than for problems without combinatorial constraints. Two modeling extensions involving the switching costs are then considered. We provide a polynomial runtime algorithm for the class of rounding problems containing (switching) costs independent of previous rounding choices and give $\mathcal{NP}$-hardness and inapproximability proofs for the class of rounding problems with (switching) cost functions dependent on previous rounding choices.