[FileFormats.MPS] another potential wrong result

[foreverdyz]

Expect for https://github.com/jump-dev/MathOptInterface.jl/issues/2469, we found that another model from MIPLIB called neos-4738912-atrato.mps generated a potential wrong result with Julia + Gurobi. We checked this file and found there was no "*". There are two issues: first, the final obj of Julia + Gurobi is slightly different to Python GRB. Though the difference is small, but considering we are using the same solver and the GAP is 0, we still think there might be an issue. Second, why the runtime for Julia + Gurobi is doubled to Python GRB? We are using the same solver (Gurobi 10.0.1) and the same device. Looks Julia + HiGHS generating the same obj to Julia + Gurobi, which are slightly different to the optimal obj from the MIPLIB website. Maybe it is another JuMP bug.

[odow]

Thanks, I'll take a look.

the final obj of Julia + Gurobi is slightly different to Python GRB

One cause might be that we don't preserve row order when reading from an MPS file in MOI.

It looks like presolve is different.

Second, why the runtime for Julia + Gurobi is doubled to Python GRB

They're solving different models.

[odow]

Oh man.

I hate this bloody format. There are so much implicit behavior.

So this is a bug. We're reading some variables as integer with free upper bound instead of 1.

[odow]

Fix is https://github.com/jump-dev/MathOptInterface.jl/pull/2480

[foreverdyz]

Hi @odow Thank you. Now I just need to remove the older JuMP and install the new one, right?

[odow]

No, you need ] add MathOptInterface#master (until I make a new release)

[foreverdyz]

Hi @odow,

Sorry to interrupt you again.

I tried ] add MathOptInterface#master; however, I found there was at least one wrong case in MIPLIB called supportcase6. The correct answer is 51906.47737 (https://miplib.zib.de/instance_details_supportcase6.html). However, both gurobi and highs returned infeasible.

Could you take a look? Thanks a lot.

[odow]

My fix in #2480 wasn't quite correct. PR incoming

[odow]

Actually. There is some ambiguity.

The variable I130051(1) appears in between a INTORG...INTEND block.

So per Gurobi "The variables introduced between a pair of markers must take integer values. All variables within markers will have a default lower bound of 0 and a default upper bound of 1 (other bounds can be specified in the BOUNDS section)."

Okay. So it is integer, and the default bounds are [0, 1].

The only other place it appears is LI BND1 I130051(1) 0 in the BOUNDS section, which says that the lower bound for the integer variable is 0. This seems superfluous, because the default lower is 0.

But I assume it also means that the default upper is ignored?

Mosek say https://docs.mosek.com/latest/capi/mps-format.html

So I would argue that this should still be [0, 1], not [0, Inf].

cc @simonbowly can you share any insight?

[simonbowly]

Ah, MPS, what fun.

But I assume it also means that the default upper is ignored?

Yes, that's the convention Gurobi follows. Specifically: if a variable is in the INTORG section, it gets a default domain of [0, 1]. If there are any bounds specified later for that variable, the default domain reverts to [0, inf] (then the specified bounds are added on top of that).

So an integer variable in [0, inf] is by written to MPS as:

NAME
ROWS
 N  OBJ
COLUMNS
    MARKER    'MARKER'                 'INTORG'
    x         OBJ       0
    MARKER    'MARKER'                 'INTEND'
RHS
BOUNDS
 LI BND1      x         0
ENDATA

The CPLEX docs seem to be the only ones that make a slightly less ambiguous statement on the topic:

If no bounds are specified for the variables within markers, bounds of 0 (zero) and 1 (one) are assumed.

[odow]

I hate this format.

FWIW, MOI always adds explicit MI or PL for unspecified bounds. No defaults.

https://github.com/jump-dev/MathOptInterface.jl/blob/eff2982a7632f710e32e5ce62b8c96393270b3b1/src/FileFormats/MPS/MPS.jl#L705-L717

[odow]

But also like. Why would you write LI BND1 x 0 instead of PL BND1 x? Surely saying "the upper bound is infinity" is more important than "the lower bound is 0, and the upper bound implicitly depends on how you interpret our documentation".

[simonbowly]

I can only speculate. Seems to be an age-old convention passed down through the generations, given that CPLEX and HIGHS appear to follow the same approach. Maybe the difference between PL x to specify [0, inf] and L1 x 1 to specify [1, inf] was considered too jarring at the time.

[odow]

Seems to be an age-old convention passed down through the generations

We need a JuMP office at ZIB...