# Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control
## 5 Recombination Heuristics
### GreedyTime  
Algorithm 2 is a routine for using the MILP solutions in a greedy pattern with the aim of constructing binary controls \(\mathbf{w}\) that exhibit an improved objective value \(\Phi(\varphi(\mathbf{w}))\). ```
Input :Control grid \(\mathcal{G}_{\omega}\), binary control vectors \(\mathbf{w}^{\text{milp}}\) as optimal solutions of \(\text{milp}\in S^{\text{CIA}}\), corresponding objectives \(\Phi(\varphi(\mathbf{w}^{\text{milp}}))\). 1 for\(j\in[M-1]_{0}\)do
2 for\((m_{1},m_{2})\in S^{\text{CIA}}\times S^{\text{CIA}},\ m_{1}\
eq m_{2},\ \mathbf{w}_{j}^{m_{1}}\
eq\mathbf{w}_{j}^{m_{2}}\)do
3 Set \(\widehat{\mathbf{w}}_{k}^{m_{1}}=\mathbf{w}_{k}^{m_{1}},k\
eq j,k\in[M-1]_{0}\) and \(\widehat{\mathbf{w}}_{j}^{m_{1}}=\mathbf{w}_{j}^{m_{2}}\);
4 Evaluate (MIOCP) with fixed \(\widehat{\boldsymbol{\omega}}^{m_{1}}=\varphi(\widehat{\mathbf{w}}^{m_{1}}) \rightarrow\Phi(\varphi(\widehat{\mathbf{w}}^{m_{1}}))\). 5 if\(\Phi(\varphi(\widehat{\mathbf{w}}^{m_{1}}))\leq\Phi(\varphi(\mathbf{w}^{m_{1}}))\)then
6 Set \(\mathbf{w}_{j}^{m_{1}}=\widehat{\mathbf{w}}_{j}^{m_{1}}\) and \(\[PERSON](\varphi(\mathbf{w}^{m_{1}}))=\[PERSON](\varphi(\widehat{\mathbf{w}}^{m_{1}}))\). 7 end if
8
9 end for return: \(\[PERSON](\varphi(\mathbf{w}^{\text{rec}})):=\min_{\text{milp}\in S^{\text{CIA}}} \[PERSON](\varphi(\mathbf{w}^{\text{milp}}))\). ```  
**Algorithm 2**GreedyTime heuristic for finding improved \(\mathbf{w}\) variables. In _GreedyTime_, we iterate over all intervals \(j\in[M-1]_{0}\) in chronological order (line 1). On every interval, we check if there are MILP pairs \((m_{1},m_{2})\) that differ in their binary control vectors in line 2. We recombine for each of these pairs the \(m_{1}\) solution with the binary control vector from \(m_{2}\) at interval \(j\) to construct a temporary control solution \(\widehat{\mathbf{w}}^{m_{1}}\) (line 3). Based on this construction, we evaluate the objective of this new control solution in line 4 and overwrite the binary control \(\mathbf{w}^{m_{1}}\) with the recombined solution \(\widehat{\mathbf{w}}^{m_{1}}\) if that latter results in an improved objective value (lines 5-6). We proceed in the same way with the second solution \(m_{2}\) when the (same) pair \((m_{2},m_{1})\) appears in the inner loop. A large number of calculated MILPs may result in a large number of pairs with unequal control solutions. In this case, it is advisable to only swap the \(\mathbf{w}^{m_{2}}\) solution with the currently smallest objective value, instead of swapping and testing each variation for every \(\mathbf{w}^{m_{1}}\). If the control problem at hand involves no continuous controls \(\mathbf{u}\), it is straightforward to evaluate the (MIOCP) in line 4 with the previously found and fixed \(\mathbf{x}\) until grid interval \(j\). This speeds up the process in problems with fine grids and numerous MILP solutions, because (MIOCP) needs to be solved iteratively. Moreover, if an MILP solution \(m_{1}\) differs from two MILPs \(m_{2},m_{3}\) with identical binary control vectors \(\mathbf{w}_{\cdot,j}^{m_{2}}=\mathbf{w}_{\cdot,j}^{m_{3}}\), it is sufficient to test the recombination with only one of the two. We illustrate an example recombination step for the pairs (CIA, SCIA) and (SCIA, CIA) in Figure 1.  
**Remark 3** (**Modifications of GreedyTime)**. :
1. _We can also apply the outer loop in Algorithm_ 2 _backward in time and name the backward version GreedyTimeBackward;_
2. _We may consider only singular arcs, instead of looping over all intervals, since the constructed binary controls are likely to be equal on bang-bung arcs. With singular arcs, we mean the intervals where_ \(\epsilon<a_{i,j}^{\ast}<1-\epsilon\) _holds for the optimal control solution_ \(\mathbf{a}^{\ast}\) _of (_OCP_), with a certain threshold_ \(\epsilon>0\)_;_
3. _Greedy-cost-to-go modification: Assume we have obtained the dual variables_ \(\tilde{\lambda}_{j,k},\ j\in[M-1]_{0},k\in[n_{x}]\)_, of the state equations of (_OCP_).