Nonserial Dynamic Programming (1972)
Link: https://www.sciencedirect.com/bookseries/mathematics-in-science-and-engineering/vol/91
Abstract: Up to the present dynamic programming has been regarded as a general type of approach to problem solving, essentially based on decomposition of the given problem into a sequence of smaller subproblems. It has permitted the solution of a remarkable number of problems (deterministic and stochastic, continuous and discrete, constrained and unconstrained, static and dynamic, and so on). In general, however, each individual situation has required derivation from the general philosophy of an ad hoc algorithm. This book, by restricting attention to the class of discrete deterministic optimization problems (constrained and unconstrained, parametric and non-parametric, serial and nonserial), aims at the following goals: (a) To give a general standard mathematical formulation for each class of problems. (b) To define, in a systematic way, three different classes of dynamic programming procedures, namely, elimination of variables one by one, elimination of variables in blocks, and multilevel elimination. The first two are a direct derivation of the principle of optimality, while the third can be regarded as a real generalization of dynamic programming. (c) To provide some simple criteria for measuring the computational effort (computing time and memory requirements) needed for each individual procedure. (d) To construct efficient algorithms, which exploit essentially graphtheoretical properties, for determining “optimal” or “good” elimination procedures (secondary optimization problem). It is worthwhile noting that some of these algorithms are also appropriate for finding efficient (i.e., requiring minimal computing time) procedures for the solution, by means of Gaussian elimination, of a system of linear equations Mz = b with M symmetric, positive definite, and sparse. The approach of this book to dynamic programming, which is, as already noted, very general, also turns out to be effective from the didactic point of view, as the authors have verified while teaching Operations Research at the Politecnico di Milano.