help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] slow matrix generation compared to AMPL


From: Andrew Makhorin
Subject: Re: [Help-glpk] slow matrix generation compared to AMPL
Date: Mon, 9 Aug 2004 19:33:06 +0400

>    I received a .mod and .dat file from a colleague using AMPL, and
>tried to run glpsol --check on it.  I've added "data;" and "end;" 
>statements where appropriate and everything worked fine.  The problem is 
>that it took over 24 hours to complete, where AMPL takes 1 minute.  I'm 
>not solving the LP, just reading the model and data.  The data file is 
>about 82MB.  My hardware is comparable to his (1 GB memory), so I don't 
>think its a case of excessive swapping. 

Could you please post me your .mod file?

>The AMPL output says there are 262,048 constraints and 555,805 
>variables.  Presolve with CPLEX eliminates 228,807 constraints and 
>390,539 variables.  I'm not planning on trying to solve the LP with 
>glpk, but thought about doing matrix generation (i.e. create an MPS file).
>
>My question is whether it would pay to profile the code to find why it 
>is so much slower than AMPL?  Could there be some poor memory management 
>issue that is causing quadratic behavior (or worse) in the matrix 
>generation phase?  Or is this more likely something very difficult to fix?

The time needed for generating model by the MathProg translator
implemented in Glpk depends not on the data size, but on the complexity
of expressions used in the model description. Unlike the AMPL system
the MathProg translator performs no optimization; it cannot do that due
to its design, since all computations are performed directly on the
parsing tree and therefore literally as constituents of the expressions
are written while (afaik) the AMPL system first translates the model
description to an intermediate code which allows optimization and then
executes it. Thus, it is sufficient to write several aggregate
expressions (like forall) nested in each other to make the generation
time arbitrarily long. I only can add that I used MathProg to generate
models with one million variables that took about 10-20 minutes on a
1.5 GHz machine.

Andrew Makhorin





reply via email to

[Prev in Thread] Current Thread [Next in Thread]