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

[Michael Hennebry]

On Sat, 24 Jul 2004, Andrew Makhorin wrote:

> >Is the format supposed to be readily readable or writeable by humans?
>
> The former, not the latter. I'm sure that to-day no one writes mps
> files by hand, although the mps format was designed to provide this.
> To-day the mps format plays the same role as object code produced by
> programming language compilers, but being very ancient, it has many
> disadvantages (intricate formatting, obsolete features which are
> actually never used like multiple vectors of rhs, using symbolic names
> as the only way to identify rows and columns which in many cases are
> simply ordinal numbers prefixed by "R" and "C", etc.). The proposed
> format is intended for the same purposes as the mps format, however,
> I tried to make it easier and more convenient for processing by
> computer program and keep its readability for human.
>
> >Allow row and col names where the corresponding numbers are allowed.
> >A name not given a specific number would get its number from the reader.
>
> This assumes that the scanner must include the symbolic name table
> while I just tried to get rid of that.

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

> >In an A line, allow a quote mark to represent the corresponding value
> >from the previous A-line.
> >A row of 1's could look something like this:
> >A  rowq  col1  1
> >A   "    col2  "
> >A   "    colc  "
> >A   "    cold  "

> Probably all this would be convenient only for human.

And real easy to implement.
It would aid in distinguishing between numbers that
were the same because they were supposed to be the same
and those that were the same by coincidence.
Also, one would be able to tell that they were the same
even if they weren't aligned.

> >I also suggest that the format include explicit rational numbers.
> >An explicit rational number would be a floating point value
> >representing an integer followed by a slash followed by
> >another floating point value representing an integer.
> >In most cases, a floating point value representing an integer
> >would be written with neither decimal point nor exponent.
> >2/3 is a allowed and so is 7/03e9 .
> >
> >When an exact representation is allowed, one need not vary
> >the representation depending on the precision of the machine.
>
> 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.

> (using, say, GNU MP library). But I'm not sure that such simplex would
> be able to solve real-world instances for a reasonable time. And while
> the simplex method is still based on floating-point computations, I do
> not see any difference between 2/3 and 0.666666666672.

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.
"2/3" could be written by a machine with 64-bit doubles and read by
a machine with 128-bit doubles.
Also, "2/3" would survive damage done by readers that
don't interpret decimal fractions as precisely as they might.


> >Allowing rational numbers is probably as
> >far as one should go in that direction.
> >Allowing arbitrary algebraic numbers would be a bit much.
> >Did someone mention trig functions?
>
> How about using roots of irreducible polynomials? :+)

Isn't that a subset of algebraic numbers?

> >This one really doesn't like I and J.
> >They often look too much alike,
> >so I often use J and K.
> >This of course causes joy when I need to
> >compare my work with that using I and J.
>
> Please explain. I don't catch.

Lower case i and j, especially when italicized, can be hard to distinguish.
In my own writing, my solution is to replace i and j by j and k respectively.

-- 
Mike   address@hidden
"Nothing says it like words if you know how to use them."
                    --  the Professional Organization of English Majors