DP2PN2Solver: A flexible dynamic programming solver software tool

• Autorzy: Mauch H.
• Języki publikacji: EN

Abstrakty

EN

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 (Lew, 2002; Lew, Mauch, 2003, 2004) 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. DP2PN2Solver's unique potential lies in its Bellman net representation. In theory, a PN's intrinsic concurrency allows to distribute the computational load encountered when solving a single DP problem instance to several computational units.

Słowa kluczowe

EN

Bellman net; dynamic programming; matrix chain multiplication problem; optimization software; Petri net model; traveling salesman problem

PL

sieć Bellmana; programowanie dynamiczne; model sieci Petri

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2006
• Tom: Vol. 35, no 3
• Strony: 687--702
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Mauch H.

• Eckerd College, Natural Sciences Collegium, 4200, 54th Ave. S., St. Petersburg, FL 33711, USA,

Bibliografia

• BILLINGTON, J., CHRISTENSEN, S., HEE, K.V., KINDLER, E., KUMMER, O., PETRUCCI, L., PETRUCCI, L., POST, R., STEHNO, C., and WEBER, M. (2003) The Petri net markup language: Concepts, technology, and tools. In: W. van der Aalst and E. Best, eds., ICATPN 2003, LNCS, 2679. Springer-Verlag, 483-505.
• HASTINGS, N. (1973) Dynamic programming with management applications. Butterworths, London, England, 1973.
• HASTINGS, N. (1974) DYNACODE dynamic programming systems handbook. Management Center, University of Bradford, Bradford, England.
• HILLIER, F.S. and LIEBERMAN, G.J. (1990) Introduction to operations research. 5th edition. McGraw-Hill Publishing Company. New York.
• HUBERT, L.J., ARABIE, P. and MEULMAN, J. (2001) Combinatorial data analysis: Optimization by dynamic programming. Society for Industrial and Applied Mathematics (SIAM). Philadelphia, PA.
• JENSEN, K. (1992) Coloured Petri Nets, Vol. 1. Springer-Verlag.
• KUMMER. O., WIENBERG, F., and DUVIGNEAU, M. (2002) Renew User Guide Release 1.6. Department of Informatics. University of Hamburg, Hamburg, Germany.
• LEW, A. (2002) A Petri net model for discrete dynamic programming. In: Proceedings of the 9th Bellman Continuum: International Workshop on Uncertain Systems and Soft Computing. Beijing, China, July 24-27, 16-21.
• LEW, A. and MAUCH, H. (2003) Solving integer dynamic programming using Petri nets. In: Proceedings of the Multiconference on Computational Engineering in Systems Applications (CESA). July 9-11, Lille, France.
• LEW, A. and MAUCH, H. (2004) Bellman nets: A Petri net model and tool for dynamic programming. In: Proceedings of Modelling, Computation and Optimization in Information Systems and Management Sciences (MCO). July 1-3, Metz, France.
• LlN. E.Y. and BRICKER, D.L. (1990) Implementing the recursive APL code for dynamic programming. APL Quote Quad 20 (4), 239-250.
• MAUCH, H. (2004) A Petri net representation for dynamic programming problems in management applications. In: Proceedings of the 37th Hawaii International Conference on System Sciences (HICSS2Q04)- January 5-8, Waikoloa, Hawaii. IEEE Computer Society.
• MURATA, T. (1989) Petri nets: Properties, analysis and applications. Proceedings of the IEEE 77 (4), 541-580.
• REISIG, W. (1985) Petri Nets: an Introduction. Springer-Verlag, Berlin.
• SNIEDOVICH, M. (1992) Dynamic programming. Marcel Dekker, Inc., New York.
• SNIEDOVICH, M. (1993) A dynamic programming algorithm for the travelling salesman problem. ACM SIC APL APL Quote Quad 23 (4), 13.
• SNIEDOVICH, M. (1994) Dynamic programming algorithms for the knapsack problem. ACM SIGAPL APL Quote Quad 24 (3), 18-21.