RE: [SUSPECTED SPAM] Re: [Help-glpk] memory usage seems very high

[Meketon, Marc]

To answer your question about error messages - there were none.  The output 
that I displayed was the complete output, with nothing stripped out.  It got as 
far as generating the "cc" constraints, and stopped.  I was using version 4.36

-----Original Message-----
From: Andrew Makhorin [mailto:address@hidden 
Sent: Saturday, June 13, 2009 12:19 PM
To: Meketon, Marc
Cc: Nicholas Farrell; help-glpk
Subject: [SUSPECTED SPAM] Re: [Help-glpk] memory usage seems very high

> 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.

---------------------------------------------------------------------------- 
This e-mail and any attachments may be confidential or legally privileged.  If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 

Thank you for your cooperation.
----------------------------------------------------------------------------