| Dynamic programming (DP) is a very general technique for solving optimization problems. In this dissertation, we develop a software system called "DP2PN2Solver" that automates many of the tasks a user encounters in order to solve an instance of a discrete optimization problem by means of DP. The user gives a specification of the DP functional equation in a special purpose high-level language. Then the specification is transformed into an intermediate Petri net (PN) representation for the discrete DP problem to be solved. After consistency checks the PN is translated into JAVA code (or some other object code that can be run in an additional step, e.g. a spreadsheet file), which solves the problem instance. Theoretical investigations examine the space of DP problems amenable to automation, as well as theory about the specialized intermediate PN representation called a "Bellman net". Bellman nets are defined in two flavors; one is based upon the high-level or colored PN definition, the other is based upon the low-level place/transition net definition. These two approaches are then put in contrast. It is shown that the novel low-level definition is sufficient for many common discrete DP problems, while the high-level definition is general enough to handle an extremely broad class of discrete DP problems. |
