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 28 Feb '14, 15:02

dassouki's gravatar image

accept rate: 0%

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 01 Mar '14, 02:28

Erling_MOSEK's gravatar image

accept rate: 3%

edited 01 Mar '14, 02:30

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 28 Feb '14, 15:02

Seen: 1,247 times

Last updated: 01 Mar '14, 02:30

OR-Exchange! Your site for questions, answers, and announcements about operations research.