# Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control
## 6 Computational Results
### Runtime Evaluation  
Figure 7 shows exemplarily the relationship between runtime and objective function values for the Lotka-Volterra multimode problem with \(N=12,\!000\) and varying \(M\). We compare (CIAmax) values both with GreedyTime and the solutions obtained by the MINLP solver Bonnin 1.8.6. For a fair comparison, we run Bonmin with its four different main algorithms, B-BB, B-OA, B-QG, and B-Hyb, and depicted the shortest runtime of these algorithms. Elapsed real time from AMPL represents runtime in our computations, since CPU time appeared to be very similar for our Bonnin calculations, and Gurobi, on the other hand, is known to be a multi-threaded solver. First of all, the illustration shows that the objective spread to the relaxed solution vanished with increasing \(M\)--regardless of the selected approach. Second, CIA was, for some instances, already quite close to Bonnin (\(M=25,50\)) in terms of objective quality, so GreedyTime cannot improve much. For other discretizations with a considerable gap between CIA and Bonnin solution, GreedyTime could close most of this gap while being two orders of magnitude faster than Bonnin.  
Figure 7: Log plot of run time and objective value deviation from the relaxed solution of the constructed solutions for different approaches and for the Lotka–Volterra multimode problem, with differential state discretization \(N=12,\!000\). The numbers in the plot indicate the applied corresponding number of control grid points \(M\). We illustrate the outcomes of the solutions constructed by (CIAmax), \(\text{Opt}(S^{\text{CIA}})\), the GreedyTime recombination heuristic, and the MINLP solver Bonnin. By \(\text{Opt}(S^{\text{CIA}})\), we denote the best objective value outcome of over all MILP solutions. For each control discretization, we connect the outcomes of the four approaches with lines in order to compare the behavior for different discretizations. One observes the convergence of all approaches towards the lower bound provided by the relaxed solution and the closure of the gap between (CIAmax) and Bonnin solutions for a fixed discretization. GreedyTime is roughly two orders of magnitude slower than (CIAmax), but is faster than Bonnin.  
The average runtime over all instances for (CIAmax) was about a few seconds and increased slightly for (SCIAmax); see Appendix A.2. [PERSON] needed on average more than one minute for the MILPs with 1-norm and thus considerably more time. For instances involving a fine discretization, the runtime increased enormously, so we set a time limit of 30 min.  
We remark that the greedy heuristics and the ArcRecombination are to be used cautiously, because an input of many MILPs leads to a high number of recombinations that have to be evaluated. ArcRecombination is relatively inexpensive and offers a solution that is at least as good as the best MILP. The algorithm is most beneficial in cases of several singular arcs, in contrast to most applied problem instances where there is only one arc. The greedy algorithm variants are quite expensive (run times of up to 15 min), yet provide solutions with objective function values very close to those of the relaxed problem.  
A way to significantly reduce the computation time of the MILPs is to apply branch-and-bound [32] or to use SUR for constructing approximate solutions. These algorithms are implemented in the open-source software package _pycombina_ (see [[https://github.com/adbuerger/pycombina](https://github.com/adbuerger/pycombina)]([https://github.com/adbuerger/pycombina](https://github.com/adbuerger/pycombina))) (accessed on 14 February 2022) [56] and might be adapted to the scaled MILP case as part of a future study. If the binary controls enter linearly into the dynamics, as in Equation (25), then the modification is straightforward, since only all differences \((a_{i}-w_{i})\) have to be scaled with the factors \(c_{i}\). Finally, run times of days, or even weeks when it comes to the MINLP solver, cast a positive light on the proposed decomposition algorithm including recombination.