[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] memory usage seems very high
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] memory usage seems very high |
Date: |
Sat, 13 Jun 2009 19:19:08 +0300 |
> A couple of strange things:
> First, when I run your model on my Windows box, it doesn #8217;t run
> completely. In particular, it generates a few of your constraints
> (c1 to cc) and then nicely stops. The output looks like:
> Reading model section from big.mod...
> 7103 lines were read
> Generating z...
> Generating c0...
> Generating c1...
> Generating c2...
> Generating c3...
> Generating c4...
> Generating c5...
> Generating c6...
> Generating c7...
> Generating c8...
> Generating c9...
> Generating ca...
> Generating cb...
> Generating cc...
> So it does not get to the optimization
> piece. I wonder if that #8217;s a window #8217;s limitation because
> you have very long lines.
Was there any error message? The mathprog translator has no limit to
the line length.
> Second, your model (from your output below) is quite small. It is fairly
> dense (30% non-zeros) but even if it was 100% dense I would expect it
> would take 10MB, not 2GB. At full density, my guess the memory formula
> would be something like: 82*5256*12*2 = 10MB: 82=number of rows,
> 5256=number of columns, 12 = size of double plus size of an int,
> 2=doubled the requirements to hold the A matrix to also hold the LU basis
> and other things. And, with the simplex algorithm, the LU factorization
> tends to be only a bit more dense than the matrix itself, so I would have
> really expected memory usage to be around 3 or 4MB.
The mathprog translator needs extra memory to store attributes of all
model objects, and it does that inefficiently. For example, every scalar
variable (or parameter) is represented as 0-dimensional array, and every
such array has an internal routine (in bytecode) used to compute its
members. Please see:
http://lists.gnu.org/archive/html/help-glpk/2008-07/msg00044.html
for some calculations about the memory requirements.
Rather than to use a lot of scalar variables it would be essentially
better to use subscripted variables. For example, instead of
. . .
var HES031008936>=0;
var HES031007598>=0;
var HES031008727>=0;
var HES031005876>=0;
var HES031009338>=0;
var HES031005658>=0;
. . .
we could use only one set and one variable subscripted over it:
set J;
var x{j in J}, >= 0;
. . .
data;
set J := ... HES031008936 HES031007598 HES031008727 HES031005876
HES031009338 HES031005658 ...
that would significantly reduce the memory used by the translator.
Another, much better way for such plain models is to use cplex lp
format.