(Gold indicates new material)
Chapter 1: Introduction
Part 1: Science Chapter 2: Fundamentals
2.1 Problem Formulation
2.2 Decomposition of the Solution Set
2.3 Principle of Conditional Optimization
2.4 Conditional Problems
2.5 Optimality Equation
2.6 Solution Procedure
2.7 Time Out: Direct Enumeration
2.8 Equivalent Conditional Problems
2.9 Modified Problems
2.10 The Role of a Decomposition Scheme
2.11 Updated Definition of a Dynamic ProgrammingProblem
2.12 Existence of Decomposition Schemes
2.13 Summary and a Look Ahead
Chapter 3: Multistage Decision Models
3.1 A Prototype Multistage Decision Model
3.2 Problem Versus Problem Formulation
3.3 Policies
3.4 Markovian Policies
3.5 Remarks on the Notation
3.6 Summary
3.7 Bibliographical Notes
Chapter 4: Dynamic Programming: an Outline
4.1 Preliminary Analysis
4.2 The Markovian Decomposition Scheme
4.3 Optimality Equation
4.4 Dynamic Programming Problems
4.5 The Final State Model
4.6 The Principle of Optimality
4.7 Summary
Chapter 5: Solving the Functional Equation
5.1 The Additive Functional Equation
5.2 Truncated Functional Equations
5.3 Nontruncated Functional Equations
5.4 Summary
Chapter 6: Successive Approximations Method
6.1 Motivational Analysis
6.2 Preliminaries
6.3 Functional Equations of Type One
6.4 Functional Equations of Type Two
6.5 Truncation Method
6.6 Stationary Models
6.7 Truncation and Successive Approximations
6.8 Summary
6.9 Bibliographical Notes
Chapter 7. Optimal Policies
7.1 Preliminary Analysis
7.2 Truncated Functional Equations
7.3 Nontruncated Functional Equations
7.4 Successive Approximations in the Policy Space
7.5 Summary
7.6 Bibliographical Notes
Chapter 8: The Curse of Dimensionality
8.1 Motivational Analysis
8.2 Discrete Problems
8.3 Direct Enumeration
8.4 Summary
Chapter 9: A Perspective on Part 1
9.1 Choice of Model
9.2 Dynamic Programming Models
9.3 Computational Schemes and Applications
9.4 Summary
Part 2: Art Chapter 10: Refinements
10.1 Weak-Markovian Condition
10.2 Ramifications of a Markovian Formulation
10.3 Composition Schemes
10.4 Sequential Decision Model
10.5 Summary
10.6 Bibliographical Notes
Chapter 11: The State
11.1 Preliminary Analysis
11.2 Mathematical Analysis
11.3 Vertices as States
11.4 Concluding remarks
11.5 Summary
11.6 Bibliographical Notes
- Chapter 12: Forward vs Backward Formulations
12.1 Preliminary Analysis
12.2 Backward Formulations
12.3 Forward Formulations
12.4 Example
12.5 Summary
- Chapter 13: Multi-Objective Problems
13.1 Preliminary Analysis
13.2 Pareto Model
13.3 Lexicographic model
13.4 Example
13.5 Summary
13.6 Bibliographical Notes
- Chapter 14: Non-Serial Models
14.1 Preliminary Analysis
14.2 Basic Non-Serial Structures
14.3 Tree model
14.4 Examples
14.5 Summary
14.6 Bibliographical Notes
- Chapter 15: Non-Optimization Models
15.1 Preliminary Analysis
15.2 Conceptunal models
15.3 Examples
15.4 Summary
15.6 Bibliographical Notes
Chapter 16: Parametric Schemes
16.1 Motivational Analysis
16.2 A Fractional/Dynamic Programming Scheme
16.3 A C-programming/Dynamic programming Scheme
16.4 The dynamic programming/Lagrange Multiplier Scheme
16.5 Summary
15.6 Bibliographical Notes
- Chapter 17: Writing Your Own DP computer Codes
17.1 Overview
17.2 General Structure of DP Codes
17.3 Recursive Codes
17.4 Non-Recursive code
17.5 Examples
17.6 Summary
17.7 Bibliographical Notes
Chapter 18: The Principle of Optimality
18.1 Background Analysis
18.2 Bellman's Principle of Optimality
18.3 Common Interpretation
18.4 Variations on a Theme
18.5 Criticism,br> 18.6 So What is Amiss?
18.7 The Final State Model Revisited
18.8 Bellman's Treatment of Dynamic Programming
18.9 Summary
18.10 Bibliographical Notes
Part 3: Epilogue Chapter 19: What Then is Dynamic Programming?
19.1 Review
19.2 An Abstract Dynamic Programming Model
19.3 Examples
19.4 The Tower of Hanoi Problem
19.5 Concluding Remarks
Appendix B: Fractional Programming
Appendix C: C-programming
Appendix D: The Principle of Optimality in Stochastic Processes
Bibliography
Index
Preface to the Second Edition
When I completed the first edition of this book back in 1991 I did not imagine that a second edition will ever be on the agenda. I guess that this was partially due to the fact that I wanted the book to have a very sharp focus.
From the response I have received from readers over the past 8 years, which I am pleased to say was mostly very positive, I have concluded that perhaps the book was too focused. For example, in the first book I deliberately did not discuss at all the very practical issue concerning the development of computer codes for dynamic programming algorithms. Apparently, this is a topic of great interest to students, lecturers and practitioners, partially because no "general purpose" dynamic programming is available.
Another example is the topic of "multi-objective optimization". It so happened that shortly after I completed the first edition I incorporated this topic in an undergraduate course entitled "Decision Making". I was surprised to see how well the topic "multicriteria shortest path problems" was received by the students and concluded that multicriteria dynamic programming was indeed an excellent teaching material.
More recently, in connection with research conducted by one of my PhD students, I had an opportunity to revisit two old favourites: backward vs forward dynamic programming and no-serial dynamic programming. I concluded that these two topics, when treated at a suitable technical level and supported by good examples, can be very instrumental in a discussion on the ultimate question: "What is Dynamic Programming?" which, you may recall, was the object of my book.
So when I was encouraged by my publisher to consider a second edition to the book, the following plan naturally emerged:
- Retain the spirit, flavor and style of the first edition, subject to minor editorial changes:
- Add new chapters on:
- Development of DP codes.
- Multiobjective Models
- Forward and Backward Formulations
- Non-Serial Models
- Non-Optimization Models
The last topic was a must given its role in the last chapter of the first edition.
So here we are: the second edition's main aim is still very much to portray dynamic programming as a methodology and is written particularly with persons teaching dynamic programming in mind. The exposition is formal, but the mathematical knowledge required for following the presentation minimal.
The four new chapters will hopefully make the presentation much more comprehensive, yet will not diminish the focus maintained by the first edition.
Preface to the First Edition
I started entertaining the idea of writing a book on dynamic programming when I first realized that in contrast to, say linear programming, there seems to be a gentlemen's disagreement as to what exactly dynamic programming is. Obviously, I envisioned a text that would offer a conclusive and incontestable formulation of dynamic programming. But I soon discovered that dynamic programming actually invites a certain amount of disagreement with respect to its definition because, by its very nature, it can be approached from a variety of angles depending on one's approach to modelling, analysis and problem solving. We thus find the intuitionist at one end, the formalist at the other, and the rest somewhere in between. So, in this book I examine the question "what is dynamic programming?'' knowing full well that whatever answer one formulates, by necessity it will be subjective in nature.
This book does not aim to portray dynamic programming as a practical tool. It does not examine how dynamic programming solves real-world problems in inventory, scheduling, sport and recreation, expert systems, etc. The book aims to give a portrait of dynamic programming as a methodology - to identify its constituent components, explain how it looks at problems, and describe how it proposes to tackle them. It should therefore appeal to readers in academia as well as to practitioners who have an interest in this facet of dynamic programming.
It should be of particular interest to readers who teach dynamic programming, as in my view, this book offers a refreshing supplement to texts which present dynamic programming from the conventional standpoint of ''Learn/Teach Dynamic Programming by Example''. These readers are advised that, although the book is not designed to serve as a course-text, because it is self-contained it can be used as ancillary reading for graduate and advanced undergraduate courses in dynamic programming.
As for my method of probing the topic. Although I fully recognize that certain aspects of dynamic programming are probably best suited for a non-formal treatment, my exposition throughout this book is strictly formal. Still, the mathematical knowledge required for following the presentation is minimal --- calculus, set theory and some optimization theory, all at the elementary level. The book does demand, however, mathematical maturity which comes into play more in modelling and formulation than in analysis.
I would like to thank my colleagues and graduate students for their helpful comments and constructive criticism on various drafts of the manuscript. I am particularly grateful to Alleli Domingo, Emmanuel Macalalag and Steven Ostrover for their comments on the final draft. I thank Ruth Dawe and Henry Boehm from Marcel Dekker Inc. for their encouragement, patience and support. And finally, special thanks are due to my wife, Shoshana, for her major contribution to this book.
Substantial work on this book was done when I was with the National Research Institute for Mathematical Sciences of the CSIR, Pretoria, South Africa.
Moshe Sniedovich
Melbourne, Australia
June, 1991
Disclaimer: This page, its contents and style, are the responsibility of the author (Moshe Sniedovich) and do not represent the views, policies or opinions of The University of Melbourne.