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

[Nigel Galloway]

Thank you. When I first read this I thought if I use --nopresol I could have 
even more numbers, say 2.5 million, which must be enough for anyone. Sadly it 
makes no difference, I presume because the optimal solution is found in the 
presol. So I'll have to make do with 1.75 million, should see me to the end of 
the month.

Thanks again,

Nigel


> ----- Original Message -----
> From: "Andrew Makhorin" <address@hidden>
> To: "Nigel Galloway" <address@hidden>
> 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
> 
> >>

>


-- 
_______________________________________________
Surf the Web in a faster, safer and easier way:
Download Opera 9 at http://www.opera.com

Powered by Outblaze