# Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control
## 6 Computational Results
### Recombination Heuristics  
We used the MILP solutions by (CIAmax), (CIA1), (SCIAmax), (\(\lambda\)CIA1), and (CIAmaxB) as a base for running the recombination heuristics on a set of 13 MIOCPs from the benchmark collection site mintoc.de with different discretizations (see Appendix A for details). The box plot in Figure 6 illustrates the numerical results with respect to objective deviation of each algorithm to the relaxed solution in percentages.  
The boxes including median values of the SCIA and backwards approaches appear to be slightly larger and their mean values and their outliers a bit smaller, respectively, than the ones of the (CIA) MILPs. The numerical study revealed several instances where (SCIAmax) or (SCIA1) ran into a binary solution with active controls on some intervals with relaxed values close to zero. Under the assumption that the combinatorial approximation is conducted mainly on singular arcs, these cases might be called _degenerated_. We experienced underperforming objective values for SCIA in case of degenerated controls, which explains some of the underperforming instances. We conclude that (SCIA1), (SCIAmax), and (CIAmaxB) should be used with caution. For specific problem classes, as shown in the previous chapters, they can be very helpful. Here, we have not specifically selected the problems, and on this general problem class there is no guarantee that these algorithms provide any real improvement.  
The solutions of (\(\lambda\)CIA1) clearly underperform, but we stress, as mentioned in Section 6.3, their importance for recombination. As a comparative calculation, we have also computed the solutions based on SUR and see that they provide similarly good, albeit somewhat worse, solutions compared with (CIA1) and (CIAmax). Note that depending on the selected algorithm, some instances resulted in a deviation of more than 100%, which can be explained by highly penalized infeasible solutions of path- or terminal-constrained problems.  
Figure 6: Box plot comparing objective deviation from the relaxed solution in percentage and log-scale of several MILP (marked in blue) and recombination heuristic (marked in red) solutions. The results are based on instances from the mintoc.de benchmark library. The box borders are \(1/4\) and \(3/4\)-quantiles, whereas the whiskers represent \(1/20\) and \(19/20\)-quantiles. We visualize the median values by black lines in the box and additionally display them numerically above the box. We represent the average values of the respective algorithms by red asterisks and the outliers by black crosses. The boxes of recombination strategies are shifted towards lower objective values compared with (CIA) algorithms and, thus, can improve the CIA decomposition performance significantly.  
The depicted recombination heuristics provide significantly better solutions in terms of the objective than the MILP-constructed binary solutions. The median values are reduced by a factor of about 2 (ArcRecombination) to a factor of 3 (GreedyTime) in comparison with (CIA). The other characteristics such as mean values, box borders, and outliers also reflect the improvements. Particularly noteworthy is the GreedyTime heuristic, which is robust against outliers as well as constructs on average solutions with small objective values. The ArcRecombination selects the solution of the MILP algorithms with the smallest objective value in the case of only one singular arc. Since many of the selected problems have only one singular arc, the box plot illustrates that this minimum over all MILPs can already provide a significant improvement.