INFORMATICA International Journal Main Page Editorial Board Abstracting/Indexing Instructions to Authors Subscription Information Contents Author Index Papers in Production		INFORMATICA, 2010, Vol. 21, No. 1, 123-138 © Institute of Mathematics and Informatics, ISSN 0868-4952 Multistage K-Means Clustering for Scenario Tree Construction Kristina SUTIENE, Dalius MAKACKAS, Henrikas PRANEVICIUS Department of Business Informatics, Kaunas University of Technology Studentu 56-301, LT-51424 Kaunas, Lithuania E-mail: kristina.sutiene@ktu.lt Abstract In stochastic programming and decision analysis, an important issue consists in the approximate representation of the multidimensional stochastic underlying process in the form of scenario tree. This paper presents the approach to generate the multistage multidimensional scenario tree out of a set of scenario fans. For this purpose, the multistage K-means clustering algorithm is developed. The presented scenario tree generation algorithm is motivated by the stability results for optimal values of a multistage stochastic program. The time complexity of developed multistage K-means clustering algorithm is proved to be linear in regard to the number of scenarios in the fan. The algorithm to determine the branches with nonduplicate information in the multistage scenario tree is also presented as an intermediate result of research. Keywords: scenario generation, scenario tree, multistage K-means clustering, time complexity To preview Lithuanian abstract see full article text To preview full article text in PDF format click here You could obtain free Acrobat Reader from Adobe
Top		Copyright © INFORMATICA, Vilnius University Institute of Mathematics and Informatics, 2010