Representation of discrete optimization problems by discrete dynamic programs
By: Douglas R. Smith
Contributors: Naval Postgraduate School (U.S.)
Publisher: Naval Postgraduate School
Published: 1980
Place of publication: Monterey, CA
Language: eng
Number of pages: 25
Subjects: Mathematical optimization; Dynamic programming
Description: This paper investigates the conditions under which a discrete optimization problem can be formulated as a dynamic program. Following the terminology of (Karp and Held 1967), a discrete optimization problem is formalized as a discrete decision problem and the class of dynamic programs is formalized as a sequential decision process. Necessary and sufficient conditions for the representation in two different senses of a discrete decision problem by a sequential decision process are established. In the first sense (a strong representation) the set of all optimal solutions to the discrete optimization problem is obtainable from the solution of the functional equations of dynamic programming. In the second sense (a weak representation) a nonempty subset of optimal solutions is obtainable from the solution of the functional equations of dynamic programming. It is shown that the well known principle of optimality corresponds to a strong representation. A more general version of the principle of optimality is given which corresponds to a weak representation of a discrete decision problem by a sequential decision process. We also show that the class of strongly representable discrete decision problems is equivalent to the class of sequential decision processes which have cost functions satisfying a strict monotonicity condition. Also a new derivation is given of the result that the class of weakly representable discrete decision problems is equivalent to the class of sequential decision processes which have a cost function satisfying a monotonicity condition. (Author)
Notes: Title from cover.

"Prepared for: Naval Postgraduate School, Monterey, California 93940." -- Cover.

"February 1980."

"NPS-52-80-004."

Includes bibliographic references (p. 24).

"Approved for public release; distribution is unlimited."

Technical report; 1980.