USING COLUMN GENERATION TECHNIQUE TO ESTIMATE PROBABILITY STATISTICS IN TRANSITION MATRIX OF LARGE SCALE MARKOV CHAIN WITH LEAST ABSOLUTE DEVIATION CRITERIA
Wanida Lerspipatthananon and Peerayuth Charnsethikul
DOI : 10.3844/jmssp.2014.331.338
Journal of Mathematics and Statistics
Volume 10, Issue 3
The Least Absolute Deviation (LAD) method is the one of many methods used to estimate transition probability matrix of Markov Chain. It can be formulated as a Linear Programming Problem (LP) and solved using its regular state of the art software. However, when the Markov Chain has a large number of states and historical state probabilities data, the corresponding LP size can be very large reaching computer hardware/software limitation. The aim of this study is to apply the Column Generation (CG) technique to solve this large scale LP and to evaluate its extension beyond direct hardware/software capabilities. In this study, the sample state probabilities data were simulated statistically and two methods were used to solve the problem. The first method was using âlinprogâ function in MATLAB to solve the related LP that all decision variables were considered simultaneously while the others was the CG method expected to require a much less percentage of all variables. As result effectiveness, both methods solved all test problems resulting equal LADs each. The CG method required more average time. Nevertheless, less than 30% of decision variables were considered in the CG method. The lesser percentages were found as the problem size grew. Moreover, larger size problems beyond direct use of software were solved using the proposed approach.
© 2014 Wanida Lerspipatthananon and Peerayuth Charnsethikul. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.