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

[Andrew Makhorin]

Michael,

Thank you very much for valuable comments.

>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.

>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  "
>
>Some problem structures would show up better this way.
>Since you specified that this is to be a low level format,
>the following suggestion is made with trepidation.
>
>A row [row...] : col [col...] value
>
>would give many matrix elements the same value.
>Allowing a 'line' to include multiple lines
>would probably be useful in this case.
>
>Another responder mentioned the importance
>of nailing down the format of a value.

Probably all this would be convenient only for human.

>I suggest the following for floating point values:
>A fixed point value optionally followed by an integer exponent.
>A 0x or 0X leading the digits in the fixed
>point value would indicate a radix of 16.
>Just a 0 would indicate base 8.
>Otherwise the radix would be 10.
>The integer exponent, if any, would indicate
>multiplication by a power of the radix.
>The exponent itself would be an e or E followed by a decimal integer.

Agree.

>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
(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.

>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? :+)

>> I row-num row-name
>
>How about
>R row-name row-num ?
>
>> J col-num col-name
>
>C col-name col-num ?

Row and column names are optional. Separate coding allows to omit
the names at all.

>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.


Andrew Makhorin