Dynamic Programming (2nd Edition)

Author: Moshe Sniedovich

Publisher: Marcel Dekker, NY

Planned Table of Contents
(Gold indicates new material)
Appendix A: Contraction Mapping
Appendix B: Fractional Programming
Appendix C: C-programming
Appendix D: The Principle of Optimality in Stochastic Processes



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:

  1. Retain the spirit, flavor and style of the first edition, subject to minor editorial changes:
  2. 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.

Last modified: Monday, 17-May-2010 23:39:18 MST

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 organizations he is associated/affiliated with.