New Approach for Nonseparable Dynamic Programming Problems

A general class of nonseparable dynamic problems is studied in a dynamic programming framework by introducing kth-order separability. The solution approach uses multiobjective dynamic programming as a separation strategy for kth-order separable dynamic problems. The theoretical grounding on which the optimal solution of the original nonseparable dynamic problem can be attained by a noninferior solution of the corresponding multiobjective dynamic programming problem is established. The relationship between the overall optimal Lagrangian multipliers and the stage-optimal Lagrangian multipliers and the relationship between the overall weighting vector and the stage weighting vector are explored, providing the basis for identifying the optimal solution of the original nonseparable problem from among the set of noninferior solutions generated by the envelope approach. © 1990 Plenum Publishing Corporation.