University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Colloquium of the Department and the PhD Program

title

Visualizing and Solving Instances of Discrete Dynamic Programming Problems given in a Special-purpose Dynamic Programming Specification Language

speaker

Prof. Dr. Holger Mauch, Eckerd College
Florida, USA

date & place

Wednesday, 11.07.2012, 15:15 h
Room Y 311

abstract

Dynamic programming (DP) is a very general technique for solving optimization problems, but surprisingly software support for the non-programming user is sparse. In this talk, a software system called ``DP2PN2Solver'' is presented. It 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 which is transformed into an intermediate Petri net (PN) representation. The intermediate graphical representation is helpful for a variety of consistency checks of the DP model provided, using either established or novel concepts from PN theory; furthermore the visualization of a DP problem has been found useful by introductory-level students who have just been introduced to the topic of DP and even by more experienced DP modelers. In a final step the intermediate PN representation is translated into solver code (e.g., plain Java, or a spreadsheet file), which solves the problem instance. Theoretical investigations examine the space of DP problems amenable to automation with our suggested approach, as well as theory about the specialized intermediate PN representation called a ``Bellman net''.