DP-solver: automating dynamic programming

Abstract

Dynamic programming (DP) is a widely used optimization method with several applications in various fields of science. The DP problem solving process can be divided in two phases: mathematical part and programming part. There are a number of researchers for whom the mathematical part is available, but they are not familiar with computer programming. In this paper we present a software tool that automates the programming part of DP and allows users to solve problems based only on their mathematical approach. The application builds up the “d-graph model” of the problem to be solved and applies the “d-variant” of the corresponding single source shortest path algorithm. In addition, we report experimental results regarding the e ciency of the tool relative to the Matlab implementation.

Keywords

• dynamic programming
• d-graphs
• software tool
• 68r15