Re: [Help-glpk] performance of exact LP solver

[Michael Hennebry]

On Thu, 20 Mar 2008, Axel Simon wrote:
> I need to use the lpx_exact function and find that the performance on
> repeatedly running a 100x10 variable problem is about 70x slower than
> using doubles. It turns out that the program spends 40% of it's time
> calculating the gcd when canonicalizing fractions. Is there a way to use
> integers (rather than rationals) to represent the coefficients of a row
> rather than rationals? I would assume that this is possible since a row
> can always be scaled by the smallest denominator. Normalizing a row
> could be much cheaper since the gcd calculation can be aborted early
> whenever the gcd drops to 1.
>
> Am I missing something?

You could end up with rather large divisors,
e.g. near the determinant of the basis.
You might try starting with doubles and feed the optimal basis to lpx_exact.

-- 
Michael   address@hidden
"Those parts of the system that you can hit with a hammer (not advised)
are called Hardware;  those program instructions that you can only
curse at are called Software."