[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Maximum number of integer variables -- is 1.75 million s
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Maximum number of integer variables -- is 1.75 million sufficient? |
Date: |
Mon, 21 Jul 2008 19:32:27 +0400 |
> 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
>>