Complexity-based implementation guidelines for Dynamic Programming: Bicriteria case

Although Dynamic Programming is one of the most used tools in optimization practice, very little is formally available as guidelines for its implementation. This paper analyses the dynamic programming implementation for totally separable problems discussing both the optimal strategy for the solution of the sub-problems and for the sequencing of such sub-problems. The results are derived in the complexity analysis tradition (i.e., worst case analysis) and the robustness of the model is discussed. In order to allow a pragmatic discussion of the effectiveness of the strategies developed under worst case assumptions, the results of a non trivial numerical experimental (704 problems) are presented.