# Integrating Pareto Optimization into Dynamic Programming
## 1 Introduction  
Pareto optimization addresses optimization under multiple, independent objectives [1]. It allows one to compute a well-defined set of extremal solutions from the search space, the Pareto front. This set holds all solutions that are optimal in one objective, in the sense that the value of the objective function cannot be improved without weakening values in other objectives. Thus, they constitute interesting trade-offs. Pareto optimization is used widely in combinatorial optimization; see [2; 3; 4] for recent applications. It is often employed, albeit in a heuristic fashion, with genetic algorithms. This happens, e.g., for biologically-motivated problems in [5; 6; 7]. Dynamic programming is a classical programming paradigm. Based on [PERSON]'s principle of optimality [8], it often allows evaluation of a search space of size \(O(2^{n})\) in polynomial time and space. Classical problems are the knapsack problem or the Floyd-Warshall algorithm [9]. Dynamic programming over sequences and tree-structured data is ubiquitous in bioinformatics [10; 11]. The combination of Pareto optimization with dynamic programming has found relatively few applications. Examples include the shortest path problem [12], the allocation problem [13], as well as some biological problems [14; 15; 16]. Although independent objectives arise frequently in bioinformatics, say balancing sequence conservation _versus_ structural similarity when aligning RNA molecules, researchers tend to shy away from using Pareto optimization and rather amalgamate theobjectives in an artificial way. This may be the case because dynamic programming algorithms are tedious to implement and debug by themselves, and dealing with multiple solutions in the Pareto way adds further coding and testing complexity. However, this situation changes with the advent of dynamic programming frameworks. Dynamic programming frameworks liberate the programmer from the tedious and error-prone coding tasks in dynamic programming. The declarative Algebraic Dynamic Programming framework (ADP) [17] addresses the needs of (bio)sequence analysis. The problem decomposition is described by a tree grammar \(\mathcal{G}\), the optimization objective by an evaluation algebra \(\mathcal{A}\) satisfying [PERSON]'s principle. These constituents given, a call in the form \(\mathcal{G}(\mathcal{A},x)\) solves the specified problem on input \(x\). The virtues are:  
1. All of the dynamic programming machinery (recurrences, for-loops, table allocation, _etc._) are generated automatically, liberating the programmer from all low-level coding and debugging. 2. Component re-use is high, since the search space and evaluation are described separately. This allows one to experiment with different search space decompositions \(\mathcal{G}_{1},\mathcal{G}_{2},\ldots\) and objectives \(\mathcal{A},\mathcal{B},\ldots\) all defined over a shared abstract data type called the signature. 3. Products of algebras can be defined such that, e.g., \(\mathcal{G}(\mathcal{A}\times\mathcal{B},x)\) solves the optimization problem under the lexicographic ordering induced by \(\mathcal{A}\) and \(\mathcal{B}\). Again, the code for the product algebra is generated automatically. Of course, the proof that an algebra \(\mathcal{A}\) satisfies [PERSON]'s principle remains the responsibility of the programmer. The ADP framework is implemented by ADP fusion [18] and [PERSON]'s GAP [19; 20]. Integration of Pareto optimization in dynamic programming is motivated by a recent theorem showing that if objectives \(\mathcal{A}\) and \(\mathcal{B}\) satisfy [PERSON]'s principle of optimality, so does their Pareto combination [21]. Therefore, a programmer can always avoid an artificial amalgamation of incommensurable scoring schemes and employ Pareto optimization instead. The theorem also allows us to extend GAP-L, the specification language of [PERSON]'s GAP, by a Pareto product operator.