A dimension-reduction algorithm for multi-stage decision problems with returns in a partially ordered set
RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 3, pp. 175-190.

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.

DOI : 10.1051/ro:2003001
Mots-clés : multi-criteria optimization, time-variant networks, dimension reduction 
@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://www.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://www.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://www.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, Tome 36 (2002) no. 3, pp. 175-190. doi : 10.1051/ro:2003001. http://www.numdam.org/articles/10.1051/ro:2003001/

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

[2] R.E. Bellman and L.A. Zadeh, Decision-Making in a Fuzzy Environment. Management Sci. 17 (1970) B-141-B-164. | MR | Zbl

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

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

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

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

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

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

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

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

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

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

[13] D.E. Kaufmann and R.L. Smith, 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).

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

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

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

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

Cité par Sources :