Iterative Aggregation-Disaggregation Procedures for Discounted Semi-Markov Reward Processes

Paul J. Schweitzer, Martin L. Puterman and Kyle W. Kindle
Additional contact information
Paul J. Schweitzer: University of Rochester, Rochester, New York
Martin L. Puterman: University of British Columbia, Vancouver, British Columbia
Kyle W. Kindle: Arthur D. Little, Inc., Cambridge, Massachusetts

Operations Research, 1985, vol. 33, issue 3, 589-605

Abstract: The equation v = q + Mv , where M is a matrix with nonnegative elements and spectral radius less than one, arises in Markovian decision processes and input-output models. In this paper, we solve the equation using an iterative aggregation-disaggregation procedure that alternates between solving an aggregated problem and disaggregating the variables, one block at a time, in terms of the aggregate variables of the other blocks. The disaggregated variables are then used to guide the choice of weights in the subsequent aggregation. Computational experiments on randomly generated and inventory problems indicate that this algorithm is significantly faster than successive approximations when the spectral radius of M is near one, and is slower in unstructured problems with spectral radii in the neighborhood of 0.8. The algorithm appears promising for large structured problems, where it can often reduce computational time and main memory storage requirements and offer greater robustness to initial values.

Keywords: 118 efficient computation; 133 efficient computation (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.3.589 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:33:y:1985:i:3:p:589-605

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().