Indices of SingleVariable constraints

[mlubin]

I propose that the constraint index of a single variable constraint should always match the index of the corresponding variable. That is,

x = add_variable(model)
ci = add_constraint(model, SingleVariable(x), ZeroOne())
# Then ci.value must equal x.value.

With this change, the question "Does x have a lower bound?" becomes is_valid(ConstraintIndex{SingleVariable, GreaterThan{Float64}}(x.value)), removing the need for JuMP to keep dictionaries (https://github.com/JuliaOpt/JuMP.jl/issues/1607#issuecomment-438219901).

It would also encourage implementations to store SingleVariable constraints in parallel arrays with the variables, which is the sane thing to do and will probably recover most of the performance from 0.18 (https://github.com/JuliaOpt/JuMP.jl/issues/1607).

This would disallow multiple SingleVariable constraints of the same type for a given variable, but that's an error on most solvers anyway.

[odow]

This seems like a reasonable proposal.

[blegat]

That would be a game changer for speeding up the @variable calls. I am in favor.

[blegat]

One issue is that you can no longer have integer variables with bounds. Or we move integrality to an attribute ?

[mlubin]

One issue is that you can no longer have integer variables with bounds. Or we move integrality to an attribute ?

Why not? ConstraintIndex{SingleVariable, GreaterThan{Float64}}(10) and ConstraintIndex{SingleVariable, Integer}(10) refer to different constraints.

[blegat]

That would work. Do we want to make this change before JuMP v0.19 ? It would mean tagging MOI v0.7.

[mlubin]

Now that we understand the issue and have a plan, this can be optional for 0.19. Does this imply any breaking API changes for JuMP? If not we can address this in 0.19.x.

[blegat]

No, the JuMP API shouldn't be affected

[blegat]

I have changed my mind about this. This change allows to store the SingleVariable constraints in a Vector instead of Dict. While this makes adding SingleVariable constraints faster, it increases the time of add_variable and the memory footprint of each variable.
Indeed, the Vector needs to have the same size than the number of variables. If we have one Vector for each MOI.AbstractScalarSet, that will be a lot of memory for each variables.

[mlubin]

I disagree that memory use is an issue with this design. JuMP 0.18 stores the lower bound, upper bound, and category for each variable, so we shouldn't be worried about storing 3 values per variable. I claim that with 2 Float64s and 1 UInt64 we can store all that we care about.

The UInt64 can store 64 boolean flags. We have less than 64 possible MOI sets that are relevant for SingleVariable constraints (and others can be handled by a slow fallback).

It can basically be:

• has lower bound
• has upper bound
• has interval (conflicts with has lower/upper and equal to)
• has equal to (conflicts with has lower/upper and interval)
• is zero one (conflicts with is integer)
• is integer (conflicts with is zero one)
• is semi-integer (conflicts with everything else and hijacks the 2 floats as the parameters of the set)
• is semicontinuous (conflicts with everything else and hijacks the 2 floats as the parameters of the set)

This is pretty close to efficient solver representations.

[blegat]

Ok then we store these 3 vectors and the MOIU.AbstractModel supports SingleVariable-in-Set for all these sets independently of the arguments of the macro. Any other SingleVariable set is handled by the UniversalFallback.
One potential other disadvantage is that in model copy, when getting ListOfConstraintIndices{SingleVariable, S}, we have to go through all the variables for each S even if there is only a constraint for one. That may not be too dramatic since checking a flag in a UInt64 is efficient.

[odow]

So this assumes that people aren't going to do silly things like deleting lots and lots of variables?

Ultimately, we're talking about a <1 sec improvement in variable creation for models with 10^6 variables. The solve time on that is going to be >> 1 s.

Can we hold off on this until after JuMP 0.19 is released? If people complain, sure.

[mlubin]

The point of the proposal is to remove a layer of indirection between SingleVariable constraints and their MOI indices, which would remove lots of Dicts from the JuMP side.

There are a number of different ways that it could be implemented. There's no real need to switch from Dicts to Vectors even though I suggested it. You could keep a Dict{VariableIndex, VariableInfo} where

struct VariableInfo
    lower_bound::Float64
    upper_bound::Float64
    flags::UInt64
end

One potential other disadvantage is that in model copy, when getting ListOfConstraintIndices{SingleVariable, S}, we have to go through all the variables for each S even if there is only a constraint for one. That may not be too dramatic since checking a flag in a UInt64 is efficient.

Yes, that is potentially an issue. Given that a full pass through the variables will be needed when ListOfConstraints is called, maybe a cache of the indices for each SingleVariable constraint could be created then.

[mlubin]

So this assumes that people aren't going to do silly things like deleting lots and lots of variables?

We don't need to change how we deal with deletion.

Ultimately, we're talking about a <1 sec improvement in variable creation for models with 10^6 variables. The solve time on that is going to be >> 1 s.

Creating integer variables with bounds is 10x slower on 0.19 than 0.18. This affects both big and small problems. It will definitely be visible in any model generation benchmarking we do.

Can we hold off on this until after JuMP 0.19 is released?

Yes that's the plan.