# Integrating Pareto Optimization into Dynamic Programming
## 4 Experiments
### Evaluation of Strategy SORT
Algorithm 5 performed second without any exceptions in the tested sets. While Algorithm 3 had appeared promising in the randomized trials, only for Prob4D could a separator be found, such that Algorithm 3 could achieve a runtime gain, even though it was significantly lower than that of Algorithm 7. Like in the randomized trials, Algorithm 6 performed consistently worse than Algorithms 2, 4, and 5, never achieving any gain. Neither input size nor front size seem to be a good indicator on which algorithm works best. Most noticeably, the largest gain over Algorithm 1 was achieved with a final front size of 13 for Fold2D. For Ali3D, there was nearly no gain, despite a much larger final front size of 446. Prob4D and Ali3D were executed on similarly-sized inputs, but only one could achieve a significant gain. The reason for these observations is that no direct statements can be made about intermediate lists and front sizes from input size or final front size alone. Pareto fronts may grow and shrink in the course of the computation. Most informative is the layout of the search space. In Figure 4, the scatter plots for Fold2D, showing the best improvement, and Gotoh2D, with no improvement, are presented. In its moderate computation time and large final front size, Gotoh2D shows only very limited variance for intermediate results. The final Pareto front consists mostly of co-optimumsthat are only added in the last step of the computation and are not present for the sorting phases. Comparing the full computation times of Gotoh2D, the overall time variance is minimal. The reason for this is the \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Name** & **Input Size** & **Front Size** & **Gain (s)** & **Algorithm** & **Sort (s)** & **Pareto (s)** & **SORT(1) (s)** & **SORT(7) (s)** \\ \hline Ali2D & 509 & 487 & 59.1 & Algorithm 7 & 341.9 & 354.5 & 579.77 & **530.0** \\ Gotoh2D & 249 & 209,744 & 0 & Algorithm 7 & 0.1 & 0.1 & **29.42** & 30.3 \\ Fold2D & 509 & 15 & 26.8 & Algorithm 7 & 169.9 & 175.5 & 334.5 & **312.3** \\ Fold2D & 608 & 13 & 304.7 & Algorithm 7 & 1296.1 & 1305.8 & 2220.24 & **1833.3** \\ Prob2D & 185 & 9 & 0 & Algorithm 7 & 2.1 & 2.3 & 3.64 & **3.6** \\ Ali3D & 200 & 446 & 0.1 & Algorithm 7 & 0.3 & 1.2 & 4.97 & **4.88** \\ Fold3D & 404 & 165 & 40.7 & Algorithm 7 & 370.4 & 727.3 & 841.64 & **806.7** \\ Prob4D & 185 & 2327 & 125.1 & Algorithm 7 & 287.0 & 1947.9 & 2556.83 & **2469.8** \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Summary of computation times and metadata of test cases. Left: Isolated sorting time gains over Algorithm 1. Input length and the final size of the resulting Pareto front are given. Input size denotes the number of characters in the input sequence. Middle: Total runtimes of sorting phase and full Pareto operators, including sorting for the best algorithm. Right: SORT(1) and SORT(7) show the full running times of the basic sorted (Algorithm 1, \(\mathbf{pf}_{sort}\)) and the specialized sorted (Algorithm 7, \(\mathbf{pf}_{sort}\)) implementations. problem decomposition of Gotoh2D. At most 3 sorted sublists are combined by the tree grammars, while the evaluation algebra also does not allow for much variation. In contrast, the grammars for the other applications have at least one rule that generates sublists of a length proportional to the input length. We will later revisit this analysis when comparing the runtime of all algorithms. Comparing the total running time of the isolated sorting phases and full Pareto computations shows that for almost all cases, more than half of the total computation time is spent in the Pareto operators. Gotoh2D is again the only exception, following the same rationale as above. While the sorting phases seem to take up the most time of the computations for 2-dimensional cases, the gap grows larger for higher dimensions.