Non-deterministic optimization model building

[joaquimg]

I am running the main.jl script in this PR jump-dev/open-energy-modeling-benchmarks#38

Every time I run it, I get a different mps file.

Rows are certainly and non-deterministic order:

This might be due to many reasons:

• Some bug
• Iterating in the Julia Dict (or some other collection that does not preserve ordering). OrderedDict from OrderedCollection is slower for some operations but preserves the order.

Even if the only issue is order, the models might have heavily varying solution times and might be difficult to debug.

Deterministic behavior would be ideal here.

[Tasqu]

There are a couple of places I think might cause this:

1. Our use of Dicts in storing JuMP variable and constraint references, as well as other stuff like temporal and stochastic structure information. Essentially anything we store in m.ext[:spineopt]. However, I'm not sure if/how this stuff impacts the JuMP model m generation directly.
2. Could potentially be caused by the indexing functions we use? I'm not sure if the order of entities is consistent when it is fetched from the database.

[DillonJ]

@joaquimg I also believe that these days we use parallel processing to build constraints, so I expect that can also cause changes in ordering etc. Can you confirm @manuelma ? If this potentially causes some variation in model solve time, is there any reason to expect that there is any net negative impact?

@joaquimg are you aware of the write_model_file() function? This is likely a much better method for debugging models as you get constraint and variable names.

[manuelma]

I'm probably missing something but quickly looking at the model json file I found that mip_rel_gap is set to 0.50 which maybe means 50% gap? Could that be causing the difference in solution times?

@DillonJ I don't see any reason why multithreading in building the constraints could lead to any issue regarding solve.

[DillonJ]

@manuelma @joaquimg is just talking about the model formulation... nothing about solving the model. When the mps file is written, it is not identical for the same problem

[manuelma]

@DillonJ right, I got that but thought you were asking about model solve time. So mutlithreading - as far as I can see - could be responsible for constraints being generated and possibly written to the mps in random order, but still it will always be the same model and thus solve time shouldn't be affected. I don't know what the solver does but I could imagine that the order of the rows in a matrix could result in differences in how difficult it is to fatorize it? No idea, just wild guessing...

[joaquimg]

@DillonJ That is an interesting point about parallel model building.
I have yet to look at the code in detail, but I have some comments.
In JuMP, you should not be able to call @constraint in parallel, so you are probably calling @expression in parallel, and then after the expressions are ready, you are adding the constraints with @constraint in sequential order.
In this sense, the parallel building should not generate models with non-deterministic constraint order.

@manuelma , about your gap comment, I am generating the MPS files before calling the HiGHS solve routine so they are not affected by gap parameters.

@DillonJ thanks fo the write_model_file suggestion.

[manuelma]

@joaquimg right, thank you for the clarification - I wasn't implying that the mip gap could have been affecting the MPS file, just the difference in solve times you were reporting. But that's also a guess.

To clarify, we use @build_constraint to generate the constraint objects in parallel and then add_constraint sequentially to add them to the model, to avoid all race conditions.

[joaquimg]

Perfect. What I said about @expression is valid for @build_constraint as well. Thanks.