Dynamic Programming: an overview

• Autorzy: Sniedovich M.
• Języki publikacji: EN

Abstrakty

EN

Dynamic programing is one of the major problem-solving methodologies in a number of disciplines such as operations research and computer science. It is also a very important and powerful tool of thought. But not all is well on the dynamic programming front. There is definitely lack of commercial software support and the situation in the classroom is not as good as it should be. In this paper we take a bird's view of dynamic programming so as to identify ways to make it more accessible to students, academics and practitioners alike.

Słowa kluczowe

EN

dynamic programming; principle of optimality; curse of dimensionality; successive approximation; push; pull

PL

programowanie dynamiczne

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

Twórcy

autor

Sniedovich M.

• Department of Mathematics and Statistics, The University of Melbourne, Australia,

Bibliografia

• BALAS, E. and SIMONETTI. N. (2001) Linear time dynamic programming algorithms for new classes of restricted TSP's: A computational study. INFORMS Journal on Computing 13 (1), 56-75.
• BELLMAN, R. (1957) Dynamic Programming. Princeton University Press, Princeton, New York.
• BIRD, R. and DE MOOR, O. (1997) Algebra of Programming. Prentice-Hall. New York.
• BRASSARD. G. and BRATLEY, P. (1988) Algorithmics Theory and Practice. Prentice-Hall, New York.
• BROWN, T.A. and STRAUCH, R.E. (1965) Dynamic programming in multiplicative lattices. Journal of Mathematical Analysis and Applications 12, 364-370.
• DENARDO, D.E. (2003) Dynamic Programming Models and Applications. Dover, New York.
• DIJKSTRA, E.W. (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271.
• DREYFUS, S.E. and LAW, A.M. (1977) The Art and Theory of Dynamic Programming. Academic Press, New York.
• ELLIS, D. (1955) An Abstract Setting of the Notion of Dynamic Programming, P-783. The RAND Corporation, Santa Monica, CA.
• HARTMAN, J.C. and PERRY, T.C. (2006) Approximating the solution of a dynamic, stochastic multiple knapsack problem. Control and Cybernetics 35 (3), 535-550.
• LEW, A. (2000) N degrees of separation: Influences of dynamic programming on computer science. Journal of Mathematical Analysis and Applications 249, 232-242.
• LEW, A. (2002) A Petri net model for discrete dynamic programming. International Workshop on Uncertain Systems and Soft Computing, Beijing.
• LEW, A. (2006) Canonical greedy algorithms and dynamic programming. Control and Cybernetics 35 (3), 621-643.
• LEW, A. and MAUCH, H. (2006) Dynamic Programming: A computational tool. Springer, Berlin.
• MAUCH, H. (2006) DP2PN2Solver: A flexible dynamic programming solver software tool. Control and Cybernetics 35 (3), 687-702.
• MURATA, T. (1989) Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE 77, 541-580.
• POLLOCK, S.M. and SMITH, R.L. (1985) A formalism of dynamic programming. Technical Report 85-8. Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan.
• PIUNOVSKIY, A.B. (2006) Dynamic programming in constrained Markov decision processes. Control and Cybernetics 35 (3), 645-660.
• POPOVA-ZEUGMANN, L. (2006) Time Petri nets state space reduction using dynamic programming. Control and Cybernetics 35 (3), 721-748.
• RAM, B. and BABU, A.J.G. (1988) Reduction of dimensionality in dynamic programming based solution methods for nonlinear integer programming. International Journal for Mathematics and Mathematical Sciences 11 (4), 811-814.
• SNIEDOVICH, M. (1992) Dynamic Programming. Marcel Dekker, New York.
• SNIEDOVICH. M. (2002) OR/MS Games: 2. The Towers of Hanoi Problem. INFORMS Transactions on Education 3 (1), 34-51.
• SNIEDOVICH, M. (2004) Dynamic Programming Revisited: Opportunities and Challenges, 41, 1-11. In: Rubinov A. and M. Sniedovich, eds., Proceedings of ICOTA 6, December 9-11, University of Ballarat, Australia.
• SNIEDOVICH, M. (2006) Dijkstra's algorithm revisited: the dynamic programming connexion. Control and Cybernetics 35 (3), 599-620.
• SNIEDOVICH, M and VOSS, S. (2006) The corridor method: a dynamic programming inspired metaheuristic. Control and Cybernetics 35 (3), 551-578.
• TERESO, A.P., MOTA, J.R.M. and LAMEIRO, R.J.T. (2006) Adaptive resource allocation to stochastic multimodal projects: a distributed platform implementation in Java. Control and Cybernetics 35 (3), 661-686.
• VERDU S. and POOR H.V. (1987) Abstract dynamic programming models under commutative conditions. SIAM Journal of Control and Optimization 25 (4), 990-1006.
• WERNER, M. (2006) A timed Petri net framework to find optimal IRIS schedules. Control and Cybernetics 35 (3), 703-719.
• WILBAUT, C., HANAFI, S., FREVILLE, A. and BALEV, S. (2006) Tabu search: global intensificaton using dynamic programming? Control and Cybernetics 35 (3), 579-598.