Representation of discrete optimization problems by discrete dynamic programs
Smith, Douglas R.
MetadataShow full item record
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)
NPS Report NumberNPS-52-80-004
Showing items related by title, author, creator and subject.
Hall, Andrew O. (Monterey, California. Naval Postgraduate School, 1999-06);This implementation of a Legendre-Gauss-Lobatto Pseudospectral (LGLP) algorithm takes advantage of the MATLAB Graphical User Interface (GUI) and the Optimization Toolbox to allow an efficient implementation of a direct ...
Brown, Gerald G.; Rutemiller, Herbert (1977-10);Applications in operations research often employ models which contain linear functions. These linear functions may have some components (coefficients and variables) which are random. (For instance, linear functions in ...
Williams, Steven M. (Monterey, California. Naval Postgraduate School, 1995-03);This thesis work is to implement the receiver pan of the SNR high speed network transport protocol. The approach was to use the Systems of Communicating Machines (SCM) as the formal definition of the protocol. Programs ...