# Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control
## 2 Problem Class, Definitions, and Main Algorithm
For using MILPs to approximate control functions, we  
_We denote, by \(\tilde{\lambda}_{j,k}\in\mathbb{R},\ t_{j}\in\mathcal{G}_{\omega},\ k\in[n_{x}]\), the discretized and evaluated dual variables of the ODE constraints (2b) in (OCP)._  
Our decomposition algorithm is based on the algorithmic choices of the sets \(S^{\text{CIA}}\) and \(S^{\text{REC}}\), which we define next. **Definition 5** (\(\boldsymbol{S^{\text{CIA}}},\boldsymbol{S^{\text{REC}}}\)). : _We introduce the set of CIA problems \(S^{\text{CIA}}\) as:_  
\[S^{\text{CIA}}:=\{(\text{CIAmax}),(\text{CIA1}),(\text{CIAmaxB}),( \text{CIA1B}),(\lambda\text{CIA1}),(\lambda\text{CIA1B}),\] \[(\text{SCIAmax}),(\text{SCIA1}),(\text{SCIAmaxB}),(\text{SCIA1B})\},\]  
_where we define the specific CIA problems in the next section. For a subset \(\tilde{S}^{\text{CIA}}\subseteq S^{\text{CIA}}\), we denote, with \(n_{\text{CIA}}:=|S^{\text{CIA}}|\), the number of different CIA problem formulations. Let the elements of \(\tilde{S}^{\text{CIA}}\) be numbered by \(1,\ldots,n_{\text{CIA}}\). Let the set \(S^{\text{REC}}\) of recombination mappings \(F^{\text{rec}}\in S^{\text{REC}}\) be defined via:_  
\[F^{\text{rec}}:\ \underset{k\in[n_{\text{CIA}}]}{\times}\Omega_{N}\to \Omega_{N},\qquad F^{\text{rec}}\Big{(}\mathbf{w}^{1},\ldots,\mathbf{w}^{n_{ \text{CIA}}}\Big{)}\mapsto\mathbf{w}^{\text{rec}}, \tag{3}\]  
_where \(\mathbf{w}^{k}\) denotes the optimal solution of the problem \((\text{nilp})^{k}\in S^{\text{CIA}}\)._  
We propose to use Algorithm 1 to approximate the solution of (MIOCP) efficiently with a priori bounds. Relaxing (MIOCP) to (OCP) results in state and control trajectories (line 1). We solve different MILPs to approximate the relaxed controls with binary ones in lines 2-3. Their performance is evaluated in line 4 by calculating their corresponding (feasible) state trajectories and objective values. In lines 6-7, we create new candidate binary controls in several recombination heuristics based on the existing binary controls, which we evaluate as well (line 8). As a final step, we select the best-performing binary control as the solution in line 10. ```
Input :(MIOCP) instance, grid \(\mathcal{G}_{\omega}\), algorithmic choices of sets \(\tilde{S}^{\text{CIA}}\subseteq S^{\text{CIA}}\) and \(\tilde{S}^{\text{REC}}\subseteq S^{\text{REC}}\). 1 Solve (OCP) \(\to\ \Phi^{\text{rel}}\), \(\mathbf{x}^{*}\), \(\mathbf{\alpha}^{*}\), \(\mathbf{a}^{*}=\varphi^{-1}(\mathbf{\alpha}^{*})\). for\(\text{nilp}\in\tilde{S}^{\text{CIA}}\)do
2 Solve \(\text{nilp}\) with MILP solver \(\mathbf{a}^{*}\ \to\ \mathbf{w}^{\text{nilp}}\);
3 Simulate (MIOCP) with fixed \(\boldsymbol{\omega}^{\text{nilp}}:=\varphi(\mathbf{w}^{\text{nilp}})\ \to\ \Phi_{\text{nilp}}\), \(\mathbf{x}\);
4 end for
5 for\(F^{\text{rec}}\in\tilde{S}^{\text{REC}}\)do
6 Create \(\mathbf{w}^{\text{rec}}\) using \(F^{\text{rec}}(\mathbf{w}^{\text{nilp}})\), \(\Phi^{\text{nilp}}\) from all \(\text{nilp}\in\tilde{S}^{\text{CIA}}\);
7 Simulate (MIOCP) with fixed \(\boldsymbol{\omega}^{\text{rec}}:=\varphi(\mathbf{w}^{\text{rec}})\ \to\ \Phi^{\text{rec}}\), \(\mathbf{x}\)
8 end for
9 Find \(\text{opt}\in\tilde{S}^{\text{CIA}}\cup\tilde{S}^{\text{REC}}\) with \(\Phi^{\text{opt}}=\text{min}\Bigg{\{}\min_{\text{nilp}\in\tilde{S}^{\text{CIA }}}\Phi^{\text{nilp}},\min_{F^{\text{rec}}\in\tilde{S}^{\text{REC}}}\Phi^{\text {rec}}\Bigg{\}}\); return: \((\mathbf{x},\mathbf{w},\Phi)=(\mathbf{x}^{\text{opt}},\mathbf{w}^{\text{opt}},\Phi^{\text{opt}})\);
```  
**Algorithm 1**Decomposition of (MIOCP). The main idea of Algorithm 1 is to decouple controls and states. We approximate the relaxed control function \(\mathbf{\alpha}^{*}\) that is optimal for (OCP) with binary controls \(\boldsymbol{\omega}\), such that a good objective function value is obtained when (MIOCP) is evaluated for \(\boldsymbol{\omega}\). Which MILPs and recombination heuristics are used in the algorithm depends on the definition of the sets \(\tilde{S}^{\text{CIA}}\) and \(\tilde{S}^{\text{REC}}\), which we discuss in Sections 3 and 5.