Re: [Help-glpk] Maximum number of integer variables -- is 1.75 million sufficient?

[Andrew Makhorin]

> I know I can probably produce a better analysis of the uniformity
> of glpk's random number generator with a sample size smaller than 1.75
> million integers, but what would be the point of that?

> More interestingly is why does mathprog require a 1000 bytes per integer?

Here are some calculations.

MathProg model:

Representation of one elemental variable requires:
one struct ELEMVAR containing the variable's attributes (44 bytes);
one struct MEMBER describing the variable as a member of the array
of variables (16 bytes);
one struct TUPLE containing indices of the array member (8 bytes);
one struct SYMBOL containing the index value (12 bytes);
one struct AVLNODE describing the array member as a node of the
search tree (32 bytes).
*** Total: 112 bytes

Representation of one elemental constraint requires:
one struct ELEMCON containing the constraint's attributes (32 bytes);
one struct MEMBER (16 bytes);
one struct TUPLE (8 bytes);
one struct SYMBOL (12 bytes);
one struct AVLNODE (32 bytes);
three structs FORMULA describing constraint coefficients (3*16 bytes).
*** Total: 148 bytes

Representation of one parameter member requires:
one struct MEMBER (16 bytes);
one struct TUPLE (8 bytes);
one struct SYMBOL (12 bytes);
one struct AVLNODE (32 bytes).
*** Total: 68 bytes

LP presolver:
One constraint (struct LPPROW) requires 44 bytes;
One variable (struct LPPCOL) requires 60 bytes;
One constraint coefficient (struct LPPLFE) requires 16 bytes.

Glp_prob problem object:
One constraint (struct GLPROW) requires 92 bytes;
One variable (struct GLPCOL) requires 104 bytes;
One constraint coefficient (struct GLPAIJ) requires 32 bytes.
Since the MathProg translator provides symbolic names of rows and
columns, which are copied to the problem object, one row/column
also requires 32 bytes (struct AVLNODE) and about 8 bytes for its
symbolic name.

Note, if the LP presolver is used, there are two problem objects.

Thus,
one variable requires 112 + 60 + 2*104 + 2*32 + 2*8 = 460 bytes;
one constraint requires 148 + 44 + 2*92 + 2*32 + 2*8 = 456 bytes;
one coefficient requires 16 + 2*32 = 80 bytes;
one parameter member requires 68 bytes.

If you have 1,500,000 variables, constraints, parameters and
non-zero coefficients in your model, you need about
1,500,000 * (460 + 456 + 80 + 68) ~= 1,500,000 * 1064 ~= 1522Mb
of memory.

> /*Arithmetic Mean of a large number of random Integers
>    between 1 and 9 inclusive should be 5. The sum over each
>    (random Integer - 5) should be 0, is it for glpk's psudo random
>    generator?
>   - or - another excuse to solve a very large constraint matrix
>          over 1.75 million integers with 2GB of memory.
>   address@hidden
>   July 18th., 2008.
> */

> param e := 1750000;
> param Sample {x in 1..e} := floor(Uniform(1,10)),integer;
> var Mean := 5;
> var E {x in 1..e},integer;

> /* Mean + variance[n] = Sample[n] */
> variances{z in 1..e}: Mean + E[z] = Sample[z];

> solve;

> printf "%d\n", sum{x in 1..e} E[x];

> end;


C:\Users\Nigel\glpk>>glpsol --math Mean\randomtest.mathprog
> Reading model section from Mean\randomtest.mathprog...
> 20 lines were read
> Generating variances...
> Model has been successfully generated
> glp_simplex: original LP has 1500000 rows, 1500000 columns, 1500000 non-zeros
> Objective value = 0
> OPTIMAL SOLUTION FOUND BY LP PRESOLVER
> Integer optimization begins...
> +     0: mip =     not found yet >=              -inf        (1; 0)
+     0: >>>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (1; 0)
> +     0: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 1)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used:   8.0 secs
> Memory used: 1511.3 Mb (1584708640 bytes)
> -4730
> Model has been successfully processed

C:\Users\Nigel\glpk>>glpsol --math Mean\randomtest.mathprog
> Reading model section from Mean\randomtest.mathprog...
> 20 lines were read
> Generating variances...
> Model has been successfully generated
> glp_simplex: original LP has 1750000 rows, 1750000 columns, 1750000 non-zeros
> Objective value = 0
> OPTIMAL SOLUTION FOUND BY LP PRESOLVER
> Integer optimization begins...
> +     0: mip =     not found yet >=              -inf        (1; 0)
+     0: >>>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (1; 0)
> +     0: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 1)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used:   14.0 secs
> Memory used: 1778.8 Mb (1865218544 bytes)
> -5814
> Model has been successfully processed

C:\Users\Nigel\glpk>>glpsol --math Mean\randomtest.mathprog
> Reading model section from Mean\randomtest.mathprog...
> 20 lines were read
> Generating variances...
> Model has been successfully generated
> glp_simplex: original LP has 2000000 rows, 2000000 columns, 2000000 non-zeros
> Objective value = 0
> OPTIMAL SOLUTION FOUND BY LP PRESOLVER
> Integer optimization begins...
> +     0: mip =     not found yet >=              -inf        (1; 0)
> xmalloc: no memory available

> Abnormal program termination



>> ----- Original Message -----
>> From: mbanco <address@hidden>
>> To: address@hidden
>> Subject: [Help-glpk] Maximum number of integer variables
>> Date: Thu, 17 Jul 2008 03:53:12 -0700 (PDT)
>> 
>> 
>> 
>> Does anyone know how many integers variables can handle the glpk 4.29?
>> --
>> View this message in context: 
>> http://www.nabble.com/Maximum-number-of-integer-variables-tp18505960p18505960.html
>> Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.
>> 
>> 
>> 
>> _______________________________________________
>> Help-glpk mailing list
>> address@hidden
>> http://lists.gnu.org/mailman/listinfo/help-glpk

>>