ABSTRACT
In this introductory chapter to the Art of Dynamic Programming I round out the discussion on two matters that have immediate consequences for modeling and formulation in dynamic programming style: the Markovian Condition, and the decomposition scheme. First, I show that a weaker version of the Markovian Condition equally
ensures the validity of the functional equation, with the caveat, that the equation may not recover all the optimal solutions. This provides the justification for formulating a problem in terms of a Weak-Markovian model should such a need arise. Next, I consolidate the concept of the decomposition scheme by arranging
it according to five major categories. This furnishes a complete account of the types of schemes that one can expect to use in dynamic programming. Finally, in the second part of the chapter I define a prototype sequen-
tial decision model, which as we shall see, enables a graphic formulation of discrete optimization problems.
