# Integrating Pareto Optimization into Dynamic Programming
## 5 Conclusions
### Hand Coding Pareto Optimization into a Dynamic Programming Algorithm  
Hand coding Pareto optimization in a dynamic programming context is a major challenge. Dynamic programming algorithms are intrinsically difficult to debug, since a subscript error in the recurrences may merely lead to overlooking the optimal solution, once in a while. On top of that, one now has to deal with multiple solutions, with sorting or merge-in-placeoperations. How can one tell that some solutions should be in the Pareto front, but have been lost along the way? Here is our first advice:  
* First of all, consider the possibility of abandoning hand coding and evaluate the suitability of [PERSON]'s GAP for the purpose. Even when you have already coded the equivalent of \(\mathcal{G}(A,x)\) and \(\mathcal{G}(B,x)\), reformulating your program in ADP will be faster and less error-prone than modifying your source code towards the equivalent of \(\mathcal{G}(\mathcal{A}\mathbin{\raisebox{-1.0 pt}{\scalebox{1.0}{$\cdot$}}} \mathcal{B})\). Doing so, you get a correct Pareto implementation for free. Keep in mind that with hand coding, you also have to implement the backtracing of Pareto-optimal solutions (_i.e._, the solution candidates behind the Pareto-optimal scores), while [PERSON]'s GAP also generates the backtracing phase for you. The reminder of our advice addresses the situation where hand coding appears unavoidable.
* Aim first for an implementation of the NOSORT strategy. It is the simplest to implement and was a good choice in most of our test cases.  
* Use an abstract data type to interface recurrences and scoring functions.
* Provide separate implementations for evaluating under scoring systems \(A\) and \(B\) first, and test them thoroughly.
* Then, implement the equivalent of \((\mathcal{A}\ ^{\sim}\ \mathcal{B})\). For debugging, make use of the mathematical fact that the optima under \(A\) and \(B\) must show up as the extreme points in the Pareto front under \((\mathcal{A}\ ^{\sim}\ \mathcal{B})\).
* If efficiency is problematic and you are going to implement another strategy X, make use of the property that NOSORT and strategy X must produce the identical Pareto fronts on the same input.
* If you choose to implement a sorting strategy, keep in mind our observation that sorting algorithm performance on random data is not meaningful for deciding on its use in the dynamic programming context. Use off-the-shelf Quicksort, or Merge-in-place if memory is critical.  
Finally, users of [PERSON]'s GAP, as well a hand coding dynamic programmer should be aware of the following caveat when implementing and comparing several strategies.  
* All dynamic programming with multiple solutions is based on the law of (strict) monotonicity, which all scoring functions must obey. Floating point errors can obstruct this prerequisite with functions that mathematically obey it.  
To illustrate the above: consider computing with two decimal positions. When scores 1.00 and 1.01 are both multiplied by 0.4, they both come out as 0.40. Now, let there be sub-solutions with scores (11, 1.00) and (10, 1.01). Neither dominates the other. After extending the sub-solutions, we obtain scores (4.4, 0.40) and (4.0, 0.40). Now, the first dominates the second, and a solution is lost that should mathematically be in the Pareto front. We found that this effect does rarely show up in practice. However, it does occur occasionally, and this matters to the program developer. When you write a large test suite that tests different strategies for identical Pareto fronts, which mathematically they must deliver, be aware that occasional discrepancies may indicate rounding effects and not a flaw in your implementation.