We run a few linear programming models that generate large matrices. These matrices are usually between 1 to 2 million in rows and 4 to 10 million in columns with 10 to 15 million non zero values. Some of these models take between 1 and 5 hours to solve. Is it possible to determine how long it will take a matrix to solve in before running it? We mostly use Mosek and GNU-GLPK to solve our models.
asked
dassouki |

It is impossible to say something about the solution time given information about the number of constraints, variables and nonzeros only. The determining factor will be the position of the nonzeros in the A matrix as well as other factors. To the best of my knowledge there is no simple method to estimate the solution time of a large sparse LP. However, assuming you are using the interior point method then the iteration time will be dependent on how fast you can compute a sparse Cholesky factorization of AA'. Since the number iterations is usually less than 100 then such information helps computing an upper bound on the solution time. Estimating the Cholesky computation time can usually be done much faster than solving the problem. However, the etsimation requires sophisticated algorithms that are build into MOSEK and similar packages. Those methods would not be easy for you to use. At MOSEK we always like challenging problems so feel free to get in touch with us if you will give us some some instances we can tune on. Maybe we can make MOSEK run faster on your problems. I currently tuning the code so it is good time now.
answered
Erling_MOSEK |