Generalized Dynamic Programming for Stochastic Combinatorial Optimization
Robert L. Carraway, Thomas L. Morin, Herbert Moskowitz
Operations Research · 1989 · Volume 37 · Issue 5
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
Enable JavaScript for citation tools and additional paper interactions.