The Art of Computational Dynamic Programming

In The Art of Computational Dynamic Programming, authors Eiji Mizutani and Stuart Dreyfus describe fertile and promising areas of computational applications of dynamic programming with emphasis on discrete optimization. The book covers various recent applications of computational dynamic programming such as sequence alignment algorithms for pattern recognition, backpropagation schemes for neural-network learning, and temporaldifference reinforcement learning. The book also includes well-discussed classical problems such as machine maintenance, resource allocation, lot-sizing, and scheduling. The authors have selected those topics particularly useful for studying fundamental principles of dynamic programming and computational procedures on multi-stage problems. Discrete dynamic programming is a stage-wise optimization procedure particularly applicable to problems requiring a sequence of interrelated decisions over multiple stages. By invoking what Richard Bellman called the principle of optimality, an optimal solution is obtained by the recurrence relations of an appropriately-defined optimal value function, whose arguments determine the state space defining an associated sub-problem. The process of building up of larger optimal solutions from optimal solutions of all relevant smaller sub-problems is the fundamental technique of computational dynamic programming. Here, the proper choice of independent argument state variables is what constitutes the art of dynamic programming. The Art of Computational Dynamic Programming conveys the role of art for designing efficient correct dynamic programming procedures in various settings that follow. To facilitate the proper state-space determination, the authors call attention to the necessity of following the general heuristic procedure called consultant questions. Imagine that a decision maker has been making sequential decisions for a while and then hires you as a consultant at the start of the current stage to take over and make the remaining decisions optimally. After being told the dynamics, constraints, and costs for the problem, you ask the consultant question: "What information about the current situation at the start of the current stage would you, the consultant, need to acquire in order to advise the client on the best sequence of remaining decisions?" Variables furnishing this information are the correct argument variables for the optimal-value function. This intuitive process requires common sense and effortful cleverness as well; consequently, correct and efficient dynamic programming is an art acquired primarily through experience with examples. In practical operational planning, the number of state variables needed to describe any particular situation frequently turns out to be too large for computational treatment. Bellman called this difficulty the curse of dimensionality. However, beyond the traditional operations-research problem domain, modern computational dynamic programming has found its rightful niche in many areas of computer science and bioinformatics, where the number of state variables is often kept small. In the literature, however, some seemingly clever strategies (e.g., concatenating decisions over multiple stages or using auxiliary information) are



- Provides computational applications of Dynamic Programming with emphasis on discrete optimization

- Conveys the role of art for designing efficient and correct dynamic programming procedures in a variety of settings

- Explains how to avoid sub-optimal solution pitfalls in dynamic programming.

- Describes diverse computational applications consistently from the dynamic programming perspective, with illustrative hand calculations