help-glpk
[Top][All Lists]
Advanced

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

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


From: Andrew Makhorin
Subject: Re[3]: [Help-glpk] proposal for gnu lp/mip low-level format
Date: Wed, 28 Jul 2004 14:44:11 +0400

>If you want it human readable, using names is essential.
>Otherwise, it will be like object code.  Even assembly uses names.

I don't think that using names is essential. Even if names are used,
as in mps, and even they are meaningful, nobody is able to "read"
(i.e. to understand) a constraint matrix having more than several tens
of rows and columns (unlike the assembly code which is more mnemonic
than symbolic). Under readability I understand that one is able to
identify which column is non-negative, which row is equality constraint,
etc., not more.

I do not pretend the proposed format to be "state-of-the-art". Its
prototype is dimacs formats for coding some classes of combinatoral
problem instances. Files in such formats can be easily created and
processed even in fortran 77 (and even in Algol 60 :+).

>And real easy to implement.

I'm talking not about implementation. Files in the proposed format
are created by computer program, so I see no reason to have features
which are suitable only for human.

>I'm not suggesting that rationals be used internally.
>As you noted, multi-precision is too slow.

Using multi-precision change nothing while using rationals change
everything. The point is that no lp/mip floating-point solver can
guarantee that the obtained optimal solution is really optimal even
if all problem data are exact (say, integer). Btw, I met somewhere
(unfortunately, don't remember where) an implementation based on
rational numbers which allows to check lp optimality conditions.

>I think that the difference would show up for 64-bit doubles.
>If double is 128 bits, I'm sure the difference would show up.

Even using other C compiler (and even changing optimization option for
the same C compiler) involves the difference. So, coding data as
rational numbers is unable to resolve the problem, i.e. to proivide
identical results for different platforms/compilers.

>Isn't that a subset of algebraic numbers?

It is the definition of algebraic numbers.


Andrew Makhorin






reply via email to

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