USING COLUMN GENERATION TECHNIQUE TO ESTIMATE PROBABILITY STATISTICS IN TRANSITION MATRIX OF LARGE SCALE MARKOV CHAIN WITH LEAST ABSOLUTE DEVIATION CRITERIA
- 1 Kasetsart University, Thailand
Abstract
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.
DOI: https://doi.org/10.3844/jmssp.2014.331.338
Copyright: © 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.
- 3,235 Views
- 2,209 Downloads
- 0 Citations
Download
Keywords
- Transition Matrix
- Markov Chain
- Linear Programming Problem
- Column Generation
- Least Absolute Deviation