Applications and solution algorithms for dynamic programming

Dynamic programming is a very flexible approach to sequential decision problems, which splits up the problem into a series of single decision problems. The possible states of the system at each decision point are classified and the effects of the possible actions on each state defined in terms of an immediate reward or cost and a probability of which state the system will be in at the next decision point. The optimal actions are then found by solving the optimality equation. The limitation of using dynamic programming in real problems relates to the large size of the state space which occurs-the ‘curse of dimensionality’ as it is called. Hereafter the paper discusses three real applications of dynamic programming which lead to large state spaces-behavioural scoring in credit control, search patterns in search and rescue, and the control of reservoir systems. The modification of existing solution algorithms for parallel computers and the development of new parallel computing solution algorithms which allow one to deal with much larger problems is also discussed.