USING COLUMN GENERATION TECHNIQUE TO ESTIMATE PROBABILITY STATISTICS IN TRANSITION MATRIX OF LARGE SCALE MARKOV CHAIN WITH LEAST ABSOLUTE DEVIATION CRITERIA

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.