Gurobi uses much less memory than I expected
Answered
Dear 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
-
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
Please sign in to leave a comment.
Comments
4 comments