Re[4]: [Help-glpk] proposal for gnu lp/mip low-level format

[Andrew Makhorin]

>> There was an idea to implement a "mathematically exact" version of the
>> simplex method which would perform all calculations in rational numbers
>
>I'm not suggesting that rationals be used internally.
>As you noted, multi-precision is too slow.

There is an exact lp solver, exlp, which is based on GNU MP library
and performs all computations in rational numbers:

http://members.jcom.home.ne.jp/masashi777/exlp.html

(There are more things in heaven and earth, Horatio, ... :+).

And it looks like the solution time is not so pessimistic even for
real-world models (I'm attaching exlp's benchmarks for netlib).
The solver's output is just fanatstic:

$ ./exlp boeing2.mps
variables: 162
rows:      166
iteration count(degenerate): 95(36)
iteration count(degenerate): 57(25)
optimal value: -6239290250177881164363943/19806093083700000000000
(-315.018728015)
size: 3/3


Andrew Makhorin

bench-steepest-edge.
Description: Binary data

bench-dual.
Description: Binary data