Gurobi uses much less memory than I expected
AnsweredDear Community,
I'm using Gurobi (interior point method) to solve a simple convex QP. The problem is as follows:
min 1/2 (Ax + By - c)^2
s.t. x>=0.
where x and y are both variables. A is an identity matrix with large size, B is a dense matrix but relatively small, and c is a constant vector.
I would expect solving the above QP with much less memory than solving a similar QP where A is also dense. However, Gurobi performs even better than I expect. It solves the QP with a memory similar to solving
min 1/2 (By - c)^2
Do you know why this is the case? Thank you in advance.
Best,
Bo
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi Bo,
It is very likely that Gurobi's presolve algorithm is able to reduce the size of the matrix by a good bit resulting in low memory usage. The log output should tell you how many row, columns, and non-zeros are present in the model Gurobi actually solves after presolve has finished.
Best regards,
Jaromił0 -
-
Hi Jaromil,
Thank you very much for the reply. Do you mind providing more information on how Gurobi reduces the size of the matrix?
Besides, I'm also confused by another Gurobi performance. When the matrix A is block diagonal (instead of being the identity matrix), the memory reduction observed in the identity matrix case is gone. The space complexity becomes O(n^2), where n is the number of variables. Why Gurobi performs differently on the block diagonal and identity matrices cases? How could Gurobi identify the matrix structure of which it can take advantage?
Best,
Bo
0 -
-
One more question. Is there a way to estimate how much memory Gurobi needs to solve a QP (with IPM)? Thank you!
Best,
Bo
0 -
-
-
Hi Bo,
Do you mind providing more information on how Gurobi reduces the size of the matrix?
The presolve reductions are discussed in the paper Presolve Reductions in Mixed Integer Programming, T. Achterberg et al. (2019).
Why Gurobi performs differently on the block diagonal and identity matrices cases? How could Gurobi identify the matrix structure of which it can take advantage?
Structure recognition is a common utility in optimization software. Recognizing certain structure allows the use of more specialized algorithms and model reductions. The identification is rather straightforward, one constructs a sparse matrix representation, checks the dimensions, entry ranges, and possibly the entry values, and tries to categorize the matrix structure if possible.
Is there a way to estimate how much memory Gurobi needs to solve a QP (with IPM)?
Unfortunately, this is currently not possible. However, you can limit the memory usage by the MemLimit parameter.
Best regards,
Jaromił0 -
Post is closed for comments.
Comments
5 comments