In this paper a two-stage algorithm for finding non- dominated subsets of partially ordered sets is established. A connection is then made with dimension reduction in time-dependent dynamic programming via the notion of a bounding label, a function that bounds the state-transition cost functions. In this context, the computational burden is partitioned between a time-independent dynamic programming step carried out on the bounding label and a direct evaluation carried out on a subset of “real” valued decisions. A computational application to time-dependent fuzzy dynamic programming is presented.

@article{RO_2002__36_3_175_0, author = {Getachew, Teodros and Kostreva, Michael M.}, title = {A dimension-reduction algorithm for multi-stage decision problems with returns in a partially ordered set}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {175--190}, publisher = {EDP-Sciences}, volume = {36}, number = {3}, year = {2002}, doi = {10.1051/ro:2003001}, mrnumber = {1988275}, zbl = {1062.90032}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro:2003001/} }

TY - JOUR AU - Getachew, Teodros AU - Kostreva, Michael M. TI - A dimension-reduction algorithm for multi-stage decision problems with returns in a partially ordered set JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2002 SP - 175 EP - 190 VL - 36 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2003001/ DO - 10.1051/ro:2003001 LA - en ID - RO_2002__36_3_175_0 ER -

%0 Journal Article %A Getachew, Teodros %A Kostreva, Michael M. %T A dimension-reduction algorithm for multi-stage decision problems with returns in a partially ordered set %J RAIRO - Operations Research - Recherche Opérationnelle %D 2002 %P 175-190 %V 36 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2003001/ %R 10.1051/ro:2003001 %G en %F RO_2002__36_3_175_0

Getachew, Teodros; Kostreva, Michael M. A dimension-reduction algorithm for multi-stage decision problems with returns in a partially ordered set. RAIRO - Operations Research - Recherche Opérationnelle, Volume 36 (2002) no. 3, pp. 175-190. doi : 10.1051/ro:2003001. http://archive.numdam.org/articles/10.1051/ro:2003001/

[1] On a Routing Problem. Quarterly Appl. Math. 16 (1958) 87-90. | MR | Zbl

,[2] Decision-Making in a Fuzzy Environment. Management Sci. 17 (1970) B-141-B-164. | MR | Zbl

and ,[3] Dynamic Programming in Multiplicative Lattices. J. Math. Anal. Appl. 12 (1965) 364-370. | MR | Zbl

and ,[4] The Shortest Route through a Network with Time-Dependent Internodal Transit Times. J. Math. Anal. Appl. 14 (1966) 493-498. | MR | Zbl

and ,[5] Shortest Paths in Networks with Vector Weights. J. Opt. Theory Appl. 46 (1985) 79-86. | MR | Zbl

and ,[6] Note on Multiple Objective Dynamic Programming. J. Oper. Res. Soc. 31 (1980) 591-594. | Zbl

and ,[7] A Note on Two Problems in Connection with Graphs. Numer. Math. 1 (1959) 269-271. | MR | Zbl

,[8] An Appraisal of Some Shortest Path Algorithms. Oper. Res. 17 (1969) 395-412. | Zbl

,[9] The Concept of “State” in Discrete Dynamic Programming. J. Math. Anal. Appl. 29 (1970) 523-557. | Zbl

,[10] A Generalization of Dynamic Programming for Pareto Optimization in Dynamic Network. RAIRO: Oper. Res. 34 (2000) 27-47. | Numdam | MR | Zbl

, and ,[11] Shortest Route with Time-Dependent Length of Edges and Limited Delay Possibilities in Nodes. Z. Oper. Res. 21 (1977) 117-124. | MR | Zbl

,[12] The Principle of Optimality in Dynamic Programming with Returns in Partially Ordered Sets. Math. Oper. Res. 10 (1985) 462-470. | MR | Zbl

,[13] Minimum Travel Time Paths in Dynamic Networks with Application to Intelligent Vehicle-Highway Systems. University of Michigan, Transportation Research Institute, Ann Arbor, Michigan, USA, IVHS Technical Report 90-11 (1990).

and ,[14] Time Dependency in Multiple Objective Dynamic Programming. J Math. Anal. Appl. 173 (1993) 289-308. | MR | Zbl

and ,[15] Shortest-Path an Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length. J. Assoc. Comp. Mach. 37 (1990) 607-625. | MR | Zbl

and ,[16] Fuzzy Dynamic Programming: Main Developments and Applications. Fuzyy Sets Sys. 81 (1996) 31-45. | MR | Zbl

and ,[17] A Fuzzy Dynamic Approach to the Multicriterion Resource Allocation Problem. Fuzzy Sets Sys. 69 (1995) 115-124. | MR

and ,*Cited by Sources: *