memory usage of models (python)

[user34]

Hi!

Using the Gurobi Python API, I'm trying to find out about memory consumption. Specifically:

1. Memory size of the model as built.

2. Max memory used during presolve.

3. Max memory used during optimization.

Is there any way to get this information using the Python interface? I would rather not parse the logfile.

Thanks!

[Tobias Achterberg]

Memory consumption is not really well defined. For example, if you allocate 1 Gigabyte of
memory but never actually use it, then the operating system doesn't care too much. On the
other hand, it could be that the nominal amount of virtual memory currently allocated by a
process is relatively low, but the actual amount of heap space that the process occupies
is large. This can happen due to memory fragmentation.

Gurobi does not provide a way to track memory consumption, and it also does not print
anything about this in the log file. But you can install a callback function and then call
operating system routines to get the memory information about the current process.

Regards,

Tobias

[Jamie Noss]

I'd very much like to know about the memory usage also, especially that used by presolve() as I have observed it to be 4x that of the Model memory usage. It is this large usage that is actually causing out of mem exceptions as noted here https://groups.google.com/forum/#!searchin/gurobi/memory/gurobi/lr2uUwcqkwU/0sTxGTCcpxcJ

[Tobias Achterberg]

Memory consumption in Gurobi is mainly driven by the non-zero elements in the constraint
matrix. To define the problem, Gurobi stores the model only in column-wise format. This
means, that each non-zero consumes 12 bytes: 4 bytes for the row index, 8 bytes for the
coefficient value.

When Gurobi goes into presolve, it needs a different and more flexible data structure to
represent the problem, and it needs a column- and a row-wise representation of the model.
This means, that each non-zero consumes about 32 bytes.

After presolve is done, the presolved model is represented again in the regular
column-wise form (12 bytes per non-zero) and the presolve data structures are discarded.
But for the solving process, Gurobi also needs a row-wise representation (another 12 bytes
per non-zero). Moreover, each parallel thread (including the master thread) needs a copy
of the model for solving LP relaxations, again with a (partial) row-wise representation.
This means another T*24 bytes, with T being the number of threads. Finally, for solving
the LP relaxation with the simplex algorithm, one needs memory to store the LU
factorization of the basis matrix. The number of non-zeros in this LU factorization
heavily depend on the structure of the model and the selection of columns in the current
basis.

So, as a summary, we have:

model construction: 12 bytes per non-zero
presolve: +32 bytes per non-zero, discarded after presolve is done
solving: +24*(T+1) bytes per non-zero + T*(size of LU factoruzation)


Regards,

Tobias

[Jamie Noss]

Awesome, thanks Tobias.

So, I'm solving an LP problem but am using the barrier method. I'm finding a few issues with the consistency between explicitly calling presolve and/or letting optimize() call presolve() (I'll open a new thread for that though).  I'm also seeing a mem consumption issue. If you look at the plot below, it appears that mem is not being discarded as you have stated. Everything post the black verticle line is either a call to Model.optimize() or Model.presolve(). Evering to the left is building and adding the constraints to the model.

Presolve called only by optimize:

gc.collect()

m.optimize()

Explicit presolve and also by optimize:

m = m.presolve()

m.Params.Presolve = 1

gc.collect()

m.optimize()

Explicit presolve, not by optimize:

m = m.presolve()

m.Params.Presolve = 0

gc.collect()

m.optimize()

The final solutions also differ by an absolute tolerance of ~>0.3.

[Tobias Achterberg]

Yes, calling presolve() expliticly is not necessarily 100% identical to the presolve that
is called implicitly when you call optimize() directly. So, you may see slightly different
memory usage patterns and different results.

Moreover, when you just call optimize(), it will at the end translate the presolved
solution back to the original model and check feasibility therein. If the solution turns
out to violate some constraints, Gurobi will try to fix those violations on the original
model. Of course, this will not be done if you pass the presolved model to optimize(),
because then, optimize() doesn't know any "original" model on which it could check
feasibility.

The barrier algorithm is typically using much more memory than the simplex algorithm,
mostly because it needs to explicitly build the AA^T system.

Tobias

[Jamie Noss]

Hi Tobias,

So, I've profiled a little further and it seems like presolve is using more memory than stated. As a function of non-zeros (nz) presolve uses ~83-86B/nz and not ~32.

I profiled 3 models that are effectively just multiples of a base problem size, i.e.  1398369272nz (base problem), 2796474168nz (~2 base), & 4194579064nz (~3 base).

Here's some data:

listed base, 2x, 3x:

B/NZ for model (pre presolve): 28.201149110875097 20.101347058822537 17.402811842194424
B/NZ max used by optimize (peaks inside presolve: (max-model)/Nnz): 126.20928239065464 83.24041911612532 83.45097549656347
B/NZ max: 154.41043150152973 103.34176617494786 100.8537873387579

presolve/model: 4.475324104505552 4.141036860491938 4.795258160191695, 32/12 = 2.67

[Tobias Achterberg]

This is an LP, and you are using barrier, right?

For LPs, we also apply a dependent row detection during presolve. This is essentially a
factorization, and we need to copy the presolve data into a different data structure to do
this efficiently. Moreover, the factorization can produce fill-in, which increases the
size a bit further.

Does the memory consumption decrease if you set the "PreDepRow" parameter to 0?


Tobias

[Jamie Noss]

Thanks for getting back to me.

Correct, it's an LP problem solving with the barrier method.

I'll try your suggestion tomorrow and get back to you.

Thanks again.

[Jamie Noss]

Nope, it has zero impact on the mem footprint.

Is this something that would be conditional on problem size?

[Jamie Noss]

Just tested this on the larger problem, no difference was observed.

[Tobias Achterberg]

Yes, in LP presolve we internally also use a different data structure, which consumes 24
bytes per non-zero. And then, every presolve reduction may create additional temporary
data structures, which might explain the memory peak. But to be really sure I would need
to profile your models.

Regards,

Tobias