Generalized Dynamic Programming for Stochastic Combinatorial Optimization

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 monot...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1989-09, Vol.37 (5), p.819-829
Main Authors: Carraway, Robert L, Morin, Thomas L, Moskowitz, Herbert
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Cities
Combinatorial optimization
Dynamic programming
dynamic programming, optimal control applications: stochastic combinatorial optimization
Exact sciences and technology
Flows in networks. Combinatorial problems
Industrial refining
Operational research and scientific management
Operational research. Management science
Optimal solutions
probability, stochastic model applications: generalized dynamic programming
Random variables
Recursion
Travel time
Traveling salesman problem
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.37.5.819