Representation of discrete optimization problems by discrete dynamic programs
Loading...
Authors
Smith, Douglas R.
Subjects
Discrete optimization
Dynamic programming
Problem representations
Dynamic programming
Problem representations
Advisors
Date of Issue
1980-02
Date
1980-02
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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)
Type
Technical Report
Description
Series/Report No
Department
Identifiers
NPS Report Number
NPS-52-80-004
Sponsors
Prepared for: Naval Postgraduate School, Monterey, California 93940. -- Cover.
Funder
Format
D, 25 p. ; 28 cm.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.