Representation of discrete optimization problems by discrete dynamic programs
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)
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.NPS Report Number
NPS-52-80-004Related items
Showing items related by title, author, creator and subject.
-
Dynamic Characteristics of Liquid Motion in Partially Filled Tanks of a Spinning Spacecraft
Agrawal, B.N. (1993);This paper presents a boundary-layer model to predict dynamic characteristics of liquid motion in partially filled tanks of a spinning spacecraft. The solution is obtained by solving three boundary-value problems: an ... -
An optimal control approach to mission planning problems: a proof of concept
Greenslade, Joseph Micheal; Karpenko, Mark (Monterey, California: Naval Postgraduate School, 2014-12);This work introduces the use of optimal control methods for simultaneous target sequencing and dynamic trajectory planning of an autonomous vehicle. This is achieved by deriving a control solution that minimizes a cost ... -
Dynamic Characteristics of Liquid Motion in Partially Filled tanks of Spinning Spacecraft
Agrawal, B.N. (1990);This paper presents a boundary layer model to predict dynamic characteristics of liquid motion in partially filled tanks of a spinning spacecraft. The solution is obtained by solving three boundary value problems: inviscid, ...