A dimension-reduction algorithm for multi-stage decision problems with returns in a partially ordered set

Teodros Getachew; Michael M. Kostreva

RAIRO - Operations Research - Recherche Opérationnelle (2002)

  • Volume: 36, Issue: 3, page 175-190
  • ISSN: 0399-0559

Abstract

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

How to cite

top

Getachew, Teodros, and 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 36.3 (2002): 175-190. <http://eudml.org/doc/245158>.

@article{Getachew2002,
abstract = {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.},
author = {Getachew, Teodros, Kostreva, Michael M.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {multi-criteria optimization; time-variant networks; dimension reduction},
language = {eng},
number = {3},
pages = {175-190},
publisher = {EDP-Sciences},
title = {A dimension-reduction algorithm for multi-stage decision problems with returns in a partially ordered set},
url = {http://eudml.org/doc/245158},
volume = {36},
year = {2002},
}

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
PB - EDP-Sciences
VL - 36
IS - 3
SP - 175
EP - 190
AB - 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.
LA - eng
KW - multi-criteria optimization; time-variant networks; dimension reduction
UR - http://eudml.org/doc/245158
ER -

References

top
  1. [1] R.E. Bellman, On a Routing Problem. Quarterly Appl. Math. 16 (1958) 87-90. Zbl0081.14403MR102435
  2. [2] R.E. Bellman and L.A. Zadeh, Decision-Making in a Fuzzy Environment. Management Sci. 17 (1970) B-141-B-164. Zbl0224.90032MR301613
  3. [3] T.A. Brown and R.E. Strauch, Dynamic Programming in Multiplicative Lattices. J. Math. Anal. Appl. 12 (1965) 364-370. Zbl0132.40303MR184776
  4. [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. Zbl0173.47601MR192921
  5. [5] H.W. Corley and I.D. Moon, Shortest Paths in Networks with Vector Weights. J. Opt. Theory Appl. 46 (1985) 79-86. Zbl0542.90099MR792595
  6. [6] H.G. Daellenbach and C.A. DeKluyver, Note on Multiple Objective Dynamic Programming. J. Oper. Res. Soc. 31 (1980) 591-594. Zbl0434.90086
  7. [7] E.W. Djikstra, A Note on Two Problems in Connection with Graphs. Numer. Math. 1 (1959) 269-271. Zbl0092.16002MR107609
  8. [8] S.E. Dreyfus, An Appraisal of Some Shortest Path Algorithms. Oper. Res. 17 (1969) 395-412. Zbl0172.44202
  9. [9] S.E. ElMaghraby, The Concept of “State” in Discrete Dynamic Programming. J. Math. Anal. Appl. 29 (1970) 523-557. Zbl0191.49201
  10. [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. Zbl0963.90055MR1747707
  11. [11] J. Halpern, Shortest Route with Time-Dependent Length of Edges and Limited Delay Possibilities in Nodes. Z. Oper. Res. 21 (1977) 117-124. Zbl0366.90116MR484343
  12. [12] M.I. Henig, The Principle of Optimality in Dynamic Programming with Returns in Partially Ordered Sets. Math. Oper. Res. 10 (1985) 462-470. Zbl0582.90104MR798391
  13. [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. [14] M.M. Kostreva and M.M. Wiecek, Time Dependency in Multiple Objective Dynamic Programming. J Math. Anal. Appl. 173 (1993) 289-308. Zbl0805.90113MR1205924
  15. [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. Zbl0699.68074MR1072271
  16. [16] J. Kacprzyk and A.O. Esogbue, Fuzzy Dynamic Programming: Main Developments and Applications. Fuzyy Sets Sys. 81 (1996) 31-45. Zbl0879.90185MR1402274
  17. [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. MR1317880

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.