More fun with lazy update semantics

[odow]

Raised on Discourse: https://discourse.julialang.org/t/jump-returning-incorrect-value-after-deleting-adding-anonymous-variable-and-constraint/38036

I don't know whether this is a bug, or expected behavior. I coded in Gurobipy and can't reproduce.

using Gurobi

function run()
    env = Gurobi.Env()
    model = Gurobi.Model(env, "")
    Gurobi.add_var!(model, Cchar('C'), 0.0, -Inf, Inf)
    Gurobi.del_vars!(model, Cint[1])
    Gurobi.add_var!(model, Cchar('C'), 0.0, -Inf, Inf)
    Gurobi.set_dblattrelement!(model, "LB", 1, 1.0)
    Gurobi.update_model!(model)
    return Gurobi.get_dblattrelement(model, "LB", 1)
end
run()  # Returns -1e100 instead of 1.

[odow]

Gurobi support say

Hi Oscar,

so I'm currently working on recreating this issue in C. In the meantime, the documentation for > GRBdelvars (see here) states that:

"Note that, due to our lazy update approach, the variables won't actually be removed until you > update the model [...]"

Given that if you run Gurobi.update_model!(model) after you deleted the variable or add the new one, it actually returns 1, I think this is not a bug on our side.

However, thank you anyways for bringing this to our attention, we will work to improve our documentation in that regard so that it becomes clearer.

I think we should probably just have a Gurobi.automatic_update() = true method that people can redefine to Gurobi.automatic_update() = false if they want to play with the advanced behavior.

[odow]

Another option is to delete a variable normally, but instead of shifting the column indices, push the variable into a set.

Then, in _update_if_necessary, you can loop through the previously deleted variables, shift the indices, and then empty the set.

[henriquebecker91]

I was studying the code yesterday to do the patch, and I think there is a pitfall in doing exactly the same thing, but saving the deleted indexes to a buffer that is traversed and emptied during the _update_if_necessary.

The add_variable(s) methods do not call _update_if_necessary, the delete methods call _update_if_necessary at the beginning already (but do not call at end and we would be trying to avoid this with this patch). To keep an appearance of 'eager' evaluation, as the JuMP API is, we delete model.variable_info eagerly (this is: at the delete call) and store the indexes in a buffer to update the columns of the values inside the model.variable_info lazily.

The problem happens in the following situation: add x_1, x_2, x_3, (calls _require_update at end); delete x_2 (_update_if_required, and then delete elements from model.variable_info but does not update their columns now, mark with _require_update); add x_4 (does not call _update_if_required, and then get the index from the length(model.variables_info), at this moment the data becomes inconsistent, because x_3 column will be 3 and x_4 column will also be 3, and when _update_if_required is called both will be changed to 2).

I am not sure if it is just a question of changing the info.column = length(model.variable_info) line to info.column = last(values(model.variables_info)).column + 1 because I am not sure what are the Gurobi columns for x_4 before calling update_model!, given x_2 (column 2) was deleted but the update was not called yet, the column used to refer to a newly created x_4 is 4 or 3? (methods adding a bound can already be called over this newly created variable and they do not call _update_if_required either, so we need to know the index in this situation).

[henriquebecker91]

I have opened a question for Gurobi support: https://support.gurobi.com/hc/en-us/community/posts/360062325771-Which-is-the-index-of-variables-added-after-variable-deletion-

[odow]

Sorry, I didn't get to this yesterday. I've already discussed with Gurobi support.

Say you have variables x and y.

In C, they will have columns 0 and 1. If you delete y and add z without updating, you are left with columns 0, 1, and 2. So, to set z lower bound, you need to modify the 2 element. Calling update deletes y properly, and shifts the columns to x, z= 0, 1.

[henriquebecker91]

Thanks. I will work on the solution with this in mind then. I just hope there is not a bug in Gurobi itself. Em seg., 4 de mai. de 2020 às 10:56, Oscar Dowson <notifications@github.com> escreveu:

…

Sorry, I didn't get to this yesterday. I've already discussed with Gurobi support. Say you have variables x and y. In C, they will have columns 0 and 1. If you delete y and add z without updating, you are left with columns 0, 1, and 2. So, to set z lower bound, you need to modify the 2 element. Calling update deletes y properly, and shifts the columns to x, z= 0, 1. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#315 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADLVVGYRYE36MNT2RJL4TRLRP3CQNANCNFSM4MOVMSZQ> .

[odow]

I'm in favor of defining

Gurobi.automatic_update() = true

_update_if_required becomes

function _update_if_requrired(model)
    if automatic_update()
        # ...
    end
end

Users can disable with Gurobi.automatic_update() = false. Then _update_if_required should be called after every deletion.

[odow]

I just hope there is not a bug in Gurobi itself.

I don't think there is. I had a longer conversation than just the thread I posted above. It's our misuse of the C API.

[henriquebecker91]

Ok. The buffer of deletions idea is to be abandoned then? None of them is specially hard to implement, I could do any of them today, I just need a decision. Also, the Gurobi.automatic_update is to be a method? This would trigger recompilation if changed, is it worth recompiling instead of having a if branching in a model attribute (if this would be model-specific), or a module global const automatic_update = RefValue{Bool}(true) to have good performance and be mutable at the same time (if we want to change the behavior of all Gurobi models at the same time). Seems to me something that would be safer to be model-specific, to avoid both changing unaware models as avoiding age-of-the-world problems.

[odow]

A model attribute would also work. Good thinking.

It depends how hard the buffer is to implement. I haven't looked in enough detail. Up to you to decide which one.

[henriquebecker91]

What is needed for the buffer is:

1. Add the buffer to the model struct and constructor.
2. Change the delete code to not update columns, instead save to buffer, move update code to inside _update_if_required.
3. Change add_variable(s) method(s) to use the column of the last variable in model.variable_info instead of using the length of model.variable_info.

I think your idea was basically right, the only thing missed is that the add_variable assumed the number of variables inside the not-synced model was the same as the number of variables in model.variable_info, but the deleted variables of the not-synced model continue counting for defining the indexes before the call to update_model!.

The model attribute is just a liitle easier because it is just a field in the model, a value in the constructor, and a if in all delete methods. I just find it a little unsatisfying because the name implies does not make clear what is automatically update, I would expect that adding variables would also trigger the automatic update.

[henriquebecker91]

I will give a try to the buffer and if I discover something I have not thought about I will consider fallbacking to the flag.

[henriquebecker91]

Just to be sure, we are talking only about variables here? I do not know if Gurobi has the same problems with deleting constraints, and the first patch will cover only variables.

[odow]

Yes, let's do variables first. Presumably there is the same issue with constraints, however.

[henriquebecker91]

There is some reason because a version 8.0.1 with this fix was not made available?