Generalized Dynamic Programming for Stochastic Combinatorial Optimization

Robert L. Carraway, Thomas L. Morin and Herbert Moskowitz
Additional contact information
Robert L. Carraway: University of Virginia, Charlottesville, Virginia
Thomas L. Morin: Purdue University, West Lafayette, Indiana
Herbert Moskowitz: Purdue University, West Lafayette, Indiana

Operations Research, 1989, vol. 37, issue 5, 819-829

Abstract: In stochastic versions of combinatorial optimization problems, the objective is to maximize or minimize a function of random variables. For many problems of this type, conventionally applied dynamic programming (DP) may fail to generate an optimal solution due to the potential violation of the monotonicity assumption of DP. We develop a generalization of DP that guarantees optimality even in the absence of monotonicity. We illustrate the methodology on a version of the stochastic traveling salesman problem for which a previously proposed DP algorithm (E. Kao) is potentially suboptimal due to the violation of monotonicity (M. Sniedovich). Using Generalized DP, we are able to modify the algorithm to guarantee optimality.

Keywords: dynamic programming; optimal control applications: stochastic combinatorial optimization; probability; stochastic model applications: generalized dynamic programming (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.37.5.819 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:37:y:1989:i:5:p:819-829

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().