A Dimension-Reduction Algorithm for Multi-Stage Decision Problems with Returns in a Partially Ordered Set

Teodros Getachew; Michael M. Kostreva

RAIRO - Operations Research (2010)

  • 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 36.3 (2010): 175-190. <http://eudml.org/doc/105269>.

@article{Getachew2010,
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},
keywords = {Multi-criteria optimization; time-variant networks dimension reduction.; multi-criteria optimization; time-variant networks; dimension reduction},
language = {eng},
month = {3},
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/105269},
volume = {36},
year = {2010},
}

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
DA - 2010/3//
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.; multi-criteria optimization; time-variant networks; dimension reduction
UR - http://eudml.org/doc/105269
ER -

References

top
  1. R.E. Bellman, On a Routing Problem. Quarterly Appl. Math. 16 (1958) 87-90.  
  2. R.E. Bellman and L.A. Zadeh, Decision-Making in a Fuzzy Environment. Management Sci.17 (1970) B-141-B-164.  
  3. T.A. Brown and R.E. Strauch, Dynamic Programming in Multiplicative Lattices. J. Math. Anal. Appl.12 (1965) 364-370.  
  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.  
  5. H.W. Corley and I.D. Moon, Shortest Paths in Networks with Vector Weights. J. Opt. Theory Appl.46 (1985) 79-86.  
  6. H.G. Daellenbach and C.A. DeKluyver, Note on Multiple Objective Dynamic Programming. J. Oper. Res. Soc.31 (1980) 591-594.  
  7. E.W. Djikstra, A Note on Two Problems in Connection with Graphs. Numer. Math.1 (1959) 269-271.  
  8. S.E. Dreyfus, An Appraisal of Some Shortest Path Algorithms. Oper. Res.17 (1969) 395-412.  
  9. S.E. ElMaghraby, The Concept of ``State'' in Discrete Dynamic Programming. J. Math. Anal. Appl.29 (1970) 523-557.  
  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.  
  11. J. Halpern, Shortest Route with Time-Dependent Length of Edges and Limited Delay Possibilities in Nodes. Z. Oper. Res.21 (1977) 117-124.  
  12. M.I. Henig, The Principle of Optimality in Dynamic Programming with Returns in Partially Ordered Sets. Math. Oper. Res.10 (1985) 462-470.  
  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.  
  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.  
  16. J. Kacprzyk and A.O. Esogbue, Fuzzy Dynamic Programming: Main Developments and Applications. Fuzyy Sets Sys.81 (1996) 31-45.  
  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.  

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.