Jump.jl: Unexpected order of variable indices

[Wikunia]

It seems like the optimizer_index indices are not returned in a deterministic fashion at least they do not only depend on JuMP/MOI but also on the solver which is unexpected.

I'll use my ConstraintSolver.jl to do the changes and show the unexpected results.

PkgVersions

• JuMP v0.21.2
• MOI v0.9.13

Model code to reproduce: https://gist.github.com/Wikunia/a16e0ebbab7cbd58058f194a9afe8dd5

If one installs the ConstraintSolver:
] add ConstraintSolver#test-1

then run include("test.jl) and test() the optimizer_index calls produce this output:

[116, 51, 131, 121, 66]
[21, 71, 56, 111, 96]
[36, 101, 46, 81, 61]
[86, 26, 146, 6, 126]
[136, 41, 106, 16, 76]
[141, 11, 31, 1, 91]
[117, 52, 132, 122, 67]
[22, 72, 57, 112, 97]
[37, 102, 47, 82, 62]
[87, 27, 147, 7, 127]
[137, 42, 107, 17, 77]
[142, 12, 32, 2, 92]

If I use ] add ConstraintSolver#test-2 afterwards + close the julia session.

I get the following result:

[1, 7, 13, 19, 25]
[2, 8, 14, 20, 26]
[3, 9, 15, 21, 27]
[4, 10, 16, 22, 28]
[5, 11, 17, 23, 29]
[6, 12, 18, 24, 30]
[31, 37, 43, 49, 55]
[32, 38, 44, 50, 56]
[33, 39, 45, 51, 57]
[34, 40, 46, 52, 58]
[35, 41, 47, 53, 59]
[36, 42, 48, 54, 60]

I expected that both results are the same as the only thing different in #test-1 and #test-2 are the order of the MOI.add_constraint function declarations.

The changes can be seen in this artificial PR: https://github.com/Wikunia/ConstraintSolver.jl/pull/157/files

I would like to remove the potential issue that this can be caused by some weird behavior I coded in my solver. Maybe someone can suggest a different way of reporting this behavior without using my solver.

My best guess: The constraint which function is defined first gets called first which could be deterministic but is still unexpected for me.

Note: I experienced this issue in a different way which I'm not really able to reproduce and here it seemed to be consistent. Hopefully some of you will be able to reproduce it.

[odow]

I could reproduce your Gurobi example:

using Gurobi, JuMP
m = Model(Gurobi.Optimizer);
@variable(m, x[1:4])
@constraint(m, x[2:3] in MOI.SOS1([1.0, 2.0]))
@constraint(m, x[3:4] in MOI.SOS1([1.0, 2.0]))
optimize!(m)
julia> optimizer_index.(x)
4-element Array{MathOptInterface.VariableIndex,1}:
 MathOptInterface.VariableIndex(3)
 MathOptInterface.VariableIndex(1)
 MathOptInterface.VariableIndex(2)
 MathOptInterface.VariableIndex(4)

It's a bit simpler as a MWE.

Edit: to clarify, the question is why the ordering 3, 1, 2, 4, which translates to x[2], x[3], x[1], x[4]. One could reasonably expect either [1, 2, 3, 4], or [2, 3, 4, 1].

[Wikunia]

But as mentioned by others this in itself is considered okay if it's deterministic. I do would prefer ordering as creation time but seems like some solvers don't support this as mentioned by @joaquimg in the developer chat.

[odow]

I don't think we have any guarantees on solver-independent ordering, since it depends on the bridges that are used.

[Wikunia]

In my cases no bridges should be used, right?

[blegat]

I guess what happens is that the variables are copied as constrained variables in SOS1. Therefore we first add constrained variables and assign to x[2], x[3]. Then we create the other ones. So the first Gurobi variable added is x[2]

[Wikunia]

Is there a way for me that in my solver I get the indices in the 1,2,3,... order ? Or access the mapping to convert to that order?

[blegat]

No, why do you need the order in which the variables were created in JuMP?

[Wikunia]

It feels like a more natural ordering which would make it easier to debug code and do reasonable benchmark tests without encountering problems as described in this issue. As mentioned I encountered this even without ordering the function declarations but can't reproduce that.

[Wikunia]

@odow

Edit: to clarify, the question is why the ordering 3, 1, 2, 4, which translates to x[2], x[3], x[1], x[4]. One could reasonably expect either [1, 2, 3, 4], or [2, 3, 4, 1].
Why [2, 3, 4, 1]? Maybe [4, 1, 2, 3]

But the actual problem for me is that I think it should only depend on JuMP and MOI not on some behavior of the solver. At least if no bridges are used.

• I think if the solver works fine with adding constraints after variables the "natural" ordering 1,...,end should be used/possible

[odow]

We really need supports_constrained_variable. JuMP should only add variables via add_constrained_variable if it is needed by the solver.

But the actual problem for me is that I think it should only depend on JuMP and MOI not on some behavior of the solver. At least if no bridges are used.

Due to MOI, we can't guarantee this anymore. How variables and constraints are added is very much a behavior of the solver.

[Wikunia]

Okay dependent on solver is also okay if the solver developer is able to choose the ordering 😬

I assumed if one implements add_constrained_variable the indices depends on the order of the constraints and one one implements add_variable + add_constraint the indices depends on the order of @variable

[odow]

Solver authors _must_ add variables in the order that they were received.
JuMP will return all_variables in the order that they were created in JuMP.

But there is no guarantee that there is a one-to-one correspondence between the variables in JuMP and the variables in the solver, and so there can be no guarantee about ordering.

[Wikunia]

I do understand that it is this way but I still believe that it shouldn't be like that.
How can I have a deterministic solver from the user point of view if my input from JuMP is not guaranteed to be ordered in some sense? Which I think is currently not given in a reasonable way as the ordering of the function declarations should not make a difference in my opinion and seems to be not intended as mentioned by @mlubin in the developer chat.

[mlubin]

I don't understand how the order of MOI.add_constraint implementations within the solver affects the order of JuMP variables. @blegat ?

[odow]

Which I think is currently not given in a reasonable way as the ordering of the function declarations should not make a difference in my opinion

This shouldn't happen. Do we have evidence of this? Ordering functions in source code shouldn't do anything.

[mlubin]

Do we have evidence of this?

This is why the issue was opened.

[odow]

Ah. This is my fault; we've been talking over each other about two different issues.

1) JuMP order doesn't match solver order
2) Non-deterministic.

Issue 2) is bad. Very bad.

[joaquimg]

I don't understand how the order of MOI.add_constraint implementations within the solver affects the order of JuMP variables. @blegat ?

The copy starts from constrained variables, and only unique variables are added. So, if two VoV share some variable the second VoV will not be added in this "adding constrained variables" phase. All the variables not added in the constrained variables phase will be added in order, and the corresponding constraints will be added as regular constraints (which will cause an error in solvers that do not support them).

That is seen in both @odow 's and @Wikunia 's test. If you switch the order of adding two (intersecting) VoV-in-set constraints the order of variables will change. If the sets are different there should be no change, but we have nothing to do in the "same set" case.

So, the order seems deterministic.

[Wikunia]

But why does JuMP cares about the order of the MOI function declarations in the solver?
Which is the case in this issue.

The order can and probably should depend on the order of the @constraint calls defined by the user.

[joaquimg]

The copy method loops in the order of F-in-S pairs that is given by the solver with: ListOfConstraints.
So I think it does not depend on the MOI function declarations in the solve but in the ListOfConstraints of the JuMP cache.

[joaquimg]

The order can and probably should depend on the order of the @constraint calls defined by the user.

I don't see why this deterministic rule is better than another deterministic rule.

For one second I forgot you have your own set, I haven't tried that.
I am not sure how the caching optimizer holds them.

[joaquimg]

Here is the definition of the copy function:
https://github.com/JuliaOpt/MathOptInterface.jl/blob/74d74433c783a980fa118ffbda1fbe9f5f0f1d8c/src/Utilities/copy.jl#L298

I think it is all related to the order that is in vector_of_variables_types

[Wikunia]

I don't know what is happening but I can't reproduce anything.
Have anyone of you tried out the setting given in this issue? Would be interested whether you get the same result as me.
I've added println(MOI.get(m, MOI.ListOfConstraints())) to see whether this is the issue.

Now I get this result with branch test-2

Tuple{DataType,DataType}[(MathOptInterface.SingleVariable, MathOptInterface.GreaterThan{Float64}), (MathOptInterface.SingleVariable, MathOptInterface.LessThan{Float64}), (MathOptInterface.SingleVariable, MathOptInterface.Integer), (MathOptInterface.VectorOfVariables, ConstraintSolver.TableSetInternal), (MathOptInterface.VectorOfVariables, ConstraintSolver.AllDifferentSetInternal)]
[136, 66, 71, 91, 96]
[86, 6, 21, 101, 61]
[141, 51, 46, 106, 131]
[11, 26, 16, 76, 111]
[81, 116, 31, 36, 146]
[126, 121, 41, 1, 56]
[137, 67, 72, 92, 97]
[87, 7, 22, 102, 62]
[142, 52, 47, 107, 132]
[12, 27, 17, 77, 112]
[82, 117, 32, 37, 147]
[127, 122, 42, 2, 57]

and this with branch test-1

Tuple{DataType,DataType}[(MathOptInterface.SingleVariable, MathOptInterface.GreaterThan{Float64}), (MathOptInterface.SingleVariable, MathOptInterface.LessThan{Float64}), (MathOptInterface.SingleVariable, MathOptInterface.Integer), (MathOptInterface.VectorOfVariables, ConstraintSolver.TableSetInternal), (MathOptInterface.VectorOfVariables, ConstraintSolver.AllDifferentSetInternal)]
[46, 76, 26, 66, 136]
[111, 116, 41, 81, 91]
[106, 71, 86, 11, 96]
[141, 126, 51, 121, 1]
[21, 146, 31, 36, 6]
[56, 16, 61, 131, 101]
[47, 77, 27, 67, 137]
[112, 117, 42, 82, 92]
[107, 72, 87, 12, 97]
[142, 127, 52, 122, 2]
[22, 147, 32, 37, 7]
[57, 17, 62, 132, 102]

They indices are in both cases different than the ones posted above without changing any code in those two branches. The ListOfConstraints are equal in both cases even with changing the function declarations so there must be something more going on.

Here the loop in https://gist.github.com/Wikunia/a16e0ebbab7cbd58058f194a9afe8dd5#file-test-jl-L18 must have a changed order in calling the TableSet constraint on my side to explain this.

As mentioned before I would prefer "natural" ordering but as you mentioned the deterministic rule is okay when it's deterministic but I can't see how this is deterministic if it doesn't depend on the user model, the solver, JuMP or MOI. It just keeps changing when I change back and forth of the branch I use.

[Wikunia]

I don't really know the general structure of how JuMP and MOI work together. @mlubin and you (@joaquimg) refer to the copy_to function and I'm wondering when this is actually called. I thought it depends on what I have here: https://github.com/Wikunia/ConstraintSolver.jl/blob/master/src/MOI_wrapper/MOI_wrapper.jl#L68-L70
but that function doesn't seem to get called in my example.

[odow]

I'm taking a deeper look at this now.

[Wikunia]

Thanks @odow and sorry I missed your question @joaquimg : I use the automatic mode so caching optimizer.

[odow]

Okay. I can reproduce this.

And I'm left with the inescapable conclusion that minor changes to functions that are never used, or even changing the order of functions in the source file, cause the ordering in a dictionary in MOI.Utilities to change.

In particular, if we comment this following line in ConstraintSolver.jl (which is never actually called):

function MOI.copy_to(model::Optimizer, src::MOI.ModelLike; kws...)
    # return MOI.Utilities.automatic_copy_to(model, src; kws...)
end

Then the order of the constraints in the UniversalFallback constraint dictionary changes:
https://github.com/JuliaOpt/MathOptInterface.jl/blob/74d74433c783a980fa118ffbda1fbe9f5f0f1d8c/src/Utilities/universalfallback.jl#L16

Coupled with MOI's weird ordering of variables based on which VectorOfVariables constraints it sees first leads to some _very_ weird results.

I guess it has something to do with the hashing of the types?

One fix seems to be to make the dictionary in UniversalFallback either Dict{Any, Dict{Any, Any}}, or an OrderedDict of some kind.

[mlubin]

AFAIK there are no guarantees on the order of keys in a Julia Dict. Switching to OrderedDict makes sense to me.

[Wikunia]

Thank you so much @odow
Glad to know that I'm not insane 😬