Re: [Help-glpk] Problem size limit?

[Nigel Galloway]

Having looked at a problem with two columns that glpk finds 
difficult here is one with over a million that it solves 
suprisingly well.

To set e to 21 should be possible with 4GB memory. Interesting to 
see if a 64-bit OS is required. 22 or more will probably need a 
professional computer.

Benchmark.mod may be included in glpk's examples if you think that 
challenging glpk is interesting.

> glpsol --math Benchmark.mod
Reading model section from Benchmark.mod...
18 lines were read
Generating zumVariance...
Generating variances...
Model has been successfully generated
glp_simplex: original LP has 1048576 rows, 1048576 columns, 3145725 non-zeros
glp_simplex: presolved LP has 1048576 rows, 1048576 columns, 3145725 non-zeros
lpx_adv_basis: size of triangular part = 1048575
       0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
       1:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   24.0 secs
Memory used: 1736.1 Mb (1820410518 bytes)
The arithmetic mean of the integers from 1 to 1048575 is 524288.000000
Model has been successfully processed

> ----- Original Message -----
> From: "Andrew Makhorin" <address@hidden>
> To: address@hidden
> Subject: Re: [Help-glpk] Problem size limit?
> Date: Tue, 18 Mar 2008 14:24:38 +0300
>
>
> > Does anyone know of a theoretical size limit for a non-integer GLPK
> > problem?
>
> Theoretically the problem size is limited by 100,000,000 rows and
> columns and 500,000,000 non-zero constraint coefficients; this is
> because glpk is a 32-bit application in the sense that it uses 32-bit
> integers to access array elements. On the other hand, glpk conforms
> to ILP32, LLP64 and LP64 programming models, i.e. it allows using
> 64-bit pointers as well, so the cumulative amount of core memory used
> may exceed 4Gb. All this, however, does not mean that glpk is able to
> solve such huge instances for a reasonable time. For pure lp instances
> the current practical limit is about one million columns and several
> millions of non-zero constraint coefficients.
>
> >   At some level, large problems may not be solvable to optimality
> > in a 'reasonable' amount of time (given available hardware).  Very,
> > very large problems may not be solveable to optimality, perhaps 
> > ever. What is GLPK's limits in terms of the number of 
> constraints > that can
> > be described, etc.  Is there a way to feed an array of data (in the
> > appropriate format) directly into GLPK instead of generating a huge
> > .MOD file that must be parsed, etc.
>
> You can feed glpk with a data file in mps or cplex lp format, or use
> the glpk api to construct the instance directly in the memory.
>
> >   Anyone care to mention how large of a problem that they have
> > solved with GLPK in terms of decision variables, constraints, etc.
>
>
>
>
> _______________________________________________
> 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

Benchmark.mod
Description: Binary data