On a biobjective search problem in a line: Formulations and algorithms

In this article we describe three formulations of a multiobjective combinatorial optimization problem, as well as several complexity results and structural properties of these formulations. A multiobjective dynamic programming algorithm is proposed for each of the three formulations. Based on our theoretical and computational results we argue that a clever definition of the recursion, allowing for strong dominance criteria, is crucial in the design of a multiobjective dynamic programming algorithm.