Article ID: | iaor20083401 |
Country: | Poland |
Volume: | 35 |
Issue: | 3 |
Start Page Number: | 687 |
End Page Number: | 702 |
Publication Date: | Jan 2006 |
Journal: | Control and Cybernetics |
Authors: | Mauch Holger |
Keywords: | networks, optimization |
Dynamic programming (DP) is a very general optimization technique, which can be applied to numerous decision problems that typically require a sequence of decisions to be made. The solver software DP2PN2Solver presented in this paper is a general, flexible, and expandable software tool that solves DP problems. It consists of modules on two levels. A level one module takes the specification of a discrete DP problem instance as input and produces an intermediate Petri net (PN) representation called Bellman net (as introduced by Art Lew, and developed by Lew and Mauch) as output – a middle layer, which concisely captures all the essential elements of a DP problem in a standardized and mathematically precise fashion. The optimal solution for the problem instance is computed by an ‘executable’ code (e.g. Java, Spreadsheet, etc.) derived by a level two module from the Bellman net representation. The unique potential of DP2PN2Solver lies in its Bellman net representation. In theory, the intrinsic concurrency of PNs allows for distributing the computational load encountered when solving a single DP problem instance to several computational units.