Parsing errors on MIPLIB mps files when using CoinUtils library.

[JoD]

Over at Exact we're using CoinUtils as parser for .mps and .lp files. This works most of the time, but for some MIPLIB mps files, CoinUtils raises errors. More info on https://gitlab.com/JoD/exact/-/issues/19 .

Any idea on what's going on? Is this behavior a non-adherence to the mps standard by MIPLIB, a bug in the CoinUtils parser, or an incorrect use of the parser on Exact's side?

[jjhforrest]

On 05/09/2022 10:18, Jo Devriendt wrote: Over at Exact we're using CoinUtils as parser for .mps and .lp files. This works most of the time, but for some MIPLIB mps files, CoinUtils raises errors. More info on https://gitlab.com/JoD/exact/-/issues/19 . Any idea on what's going on? Is this behavior a non-adherence to the mps standard by MIPLIB, a bug in the CoinUtils parser, or an incorrect use of the parser on Exact's side? —

INDICATORS seem to be a fairly recent addition to the mps format.  CoinUtils can be extended to parse the format, but I am not sure how the information should be stored.  As they are a logical version of a big M constraint, a simple idea would be to make them big M constraints but with a recognizable value for M. If this is acceptable then for INDICATORS IF constraint binary1 0 where constraint is x+y+z<=c the constraint would become x+y+z<=c+M*binary1 with M 987654321.0 It would then be up to the optimization code that knows about indicators to turn that back correctly. the case with 1 would be x+y+z<=c+M-M*binary1 Except for the case x+y+z==c the CoinUtils version would be an approximation to the correct version. Would this be acceptable - or what do you suggest?

[JoD]

The ideal case would be to have these "indicators" in fitting data structures, but I can imagine this breaks a bit too much of the row-column view of the problem that's currently used.

The second-best case would be a proper calculation of the big-M, based on the bounds of the variables. You did not mention this. Is this hard? Perhaps when some of the variables are unbounded?

The "recognizable value for M" would work in a pinch. I'm a bit worried about a user using this "flag-coefficient" unintentionally. But maybe this can be minimized by using inf or NaN or some other floating point special case value. If we need an actual number, we could go for -0 or the largest possible double or the smallest possible double (in the epsilon sense: 0.00...01).

In any case, thanks for the insight! I had no idea it was some unsupported extension to the mps format.

[JoD]

What do you mean with

Except for the case x+y+z==c the CoinUtils version would be an approximation to the correct version.

?

[jjhforrest]

On 05/09/2022 14:37, Jo Devriendt wrote: The ideal case would be to have these "indicators" in fitting data structures, but I can imagine this breaks a bit too much of the row-column view of the problem that's currently used.

Would be a lot of work - and rarely used.

The second-best case would be a proper calculation of the big-M, based on the bounds of the variables. You did not mention this. Is this hard? Perhaps when some of the variables are unbounded?

Indicators don't seem to work like that - the implicit big M should be calculated at all stages of code.

The "recognizable value for M" would work in a pinch. I'm a bit worried about a user using this "flag-coefficient" unintentionally. But maybe this can be minimized by using |inf| or |NaN| or some other floating point special case value. If we need an actual number, we could go for |-0| or the largest possible double or the smallest possible double (in the epsilon sense: 0.00...01).

I presume the user would know they were using indicators and test. I was suggesting a value which would give a reasonable continuous answer without knowing there were indicator variables - just to make it easier to pick up other errors.  Any large value would do as long as it could be defined exactly as a double - and was unlikely to happen by chance.  As to x+y+z==b - with <= or >= you can have a reasonable modified constraint - with == the new constraint would be infeasible.

…

In any case, thanks for the insight! I had no idea it was some unsupported extension to the mps format. — Reply to this email directly, view it on GitHub <#197 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABWJYHE2D5NIBH5XOYKVPLDV4XZSPANCNFSM6AAAAAAQEZQAEM>. You are receiving this because you commented.Message ID: ***@***.***>

[JoD]

Indicators don't seem to work like that - the implicit big M should be calculated at all stages of code.

Is this for the continuous case? If all variables are integral, I guess one calculation of the big M would be sufficient? I.e., Any large value would do? In any case, I trust your judgment here.

As to x+y+z==b - with <= or >= you can have a reasonable modified constraint - with == the new constraint would be infeasible.

So if I understand correctly, if we have binary1 -> (x+y+z==c), then the proposed transcription x+y+z==c+M*binary1 would not approximate the original, while for >= or =< it would? So in the == case, it would be necessary to check the M-flag to avoid incorrect answers?

Would it make sense to split the == into its >= and =< components and add the constraints for binary1 -> (x+y+z>=c) and binary1 -> (x+y+z=<c)?

Apologies for all these questions, and thanks for your explanations so far!