Use `Pair{VariableIndex, T}` instead of separate variable and coefficient lists

[odow]

Proposed by @tkoolen: In ScalarAffineFunction, why not use a Vector{Pair{VariableIndex, T}}, so as to ensure that you don’t have more coeffs than vars? Same thing for some of the other functions.

Ref #209

[joaquimg]

I don’t like Pair. I think it might be interesting having those separate vectors for inplace modifications easily. We can enforce size check on the constructor if thats a big thing

[tkoolen]

But then other methods can still push different numbers of things to each of the vectors.

[mlubin]

I agree that this is a good idea from the software engineering perspective. I would use a struct instead of a Pair (Pair doesn't generalize well to the quadratic case.)

One concern is that MOI functions usually go through mapvariables at some point in their life. This change would force us to 1) make a more expensive copy that includes the coefficients, or 2) modify the functions in place instead.

[joaquimg]

The current design is very easy to modify variable indices or the coefficients. There are cases like cut generation routines that always use the same variable indices and just changes the coefficients. Pair would make this a pain. I don´t see a big gain with that, this error is really easy to catch and solve.

[tkoolen]

I agree that a struct other than Pair would be better.

There are cases like cut generation routines that always use the same variable indices and just changes the coefficients. Pair would make this a pain.

Is that something a couple of utility functions could fix? Something like

struct LinearTerm{T}
    variable::VariableIndex
    coefficient::T
end

setvariable(term::LinearTerm, var::VariableIndex) = LinearTerm(variable, term.coefficient)
setcoefficient(term::LinearTerm, coefficient) = LinearTerm(term.variable, coefficient)

this error is really easy to catch and solve.

I disagree. It's really tempting to write code like

fun = ScalarAffineFunction([VariableIndex(1), VariableIndex(2)], [5.0, -2.3, 3.0], 1.0) # oops

for i in eachindex(fun.variables)
    fun.variables[i] = VariableIndex(3 * i)
    fun.coefficients[i] += 1
end # last coefficient wasn't updated

# and then in some completely different solver package:
for coeff in fun.coefficients
    pushontosomesolverdatastructure!(mysolver, coeff)
end

This will silently do the wrong thing due to a bug that occurred in non-local code. The only way to be sure this kind of thing doesn't happen is to tediously check that the ScalarAffineFunction is in a valid state everywhere. And then there are even more subtle cases, like erroneously removing a variable from the front of variables but removing a coefficient from the back of coefficients; now their lengths match, but they're out of sync.

One concern is that MOI functions usually go through mapvariables at some point in their life

Good point, but if speed is really a concern (which is probably the case), in my opinion mapvariables should be in-place whether or not this proposal makes it. I would expect the difference in performance between allocating a Vector{VariableIndex} and Vector{LinearTerm{T}} to be much smaller than the difference between allocating a Vector{VariableIndex} and not allocating at all.

[mlubin]

@blegat, what do you think about making map_variables work in place?

[tkoolen]

By the way, you could even have

Base.:*(variable::VariableIndex, coefficient) = LinearTerm(variable, coefficient)
Base.:*(coefficient, variable::VariableIndex) = LinearTerm(variable, coefficient)

as a way to construct these.

[mlubin]

LinearTerm.(variable, coefficient) is enough and also implicitly checks for dimension mismatches.

[blegat]

@mlubin What do you mean by "in place" ? You would do

mapvariables(varmap::Function, term::LinearTerm) = LinearTerm(varmap(term.variable), term.coefficient)
mapvariables(varmap::Function, f::MOI.ScalarAffineFunction) = MOI.ScalarAffineFunction(mapvariables(varmap, f.terms), f.coefficients, f.constant)

@tkoolen How would you adapt VectorAffineFunction ?

[mlubin]

@blegat by "in place" I mean a version that modifies the original function and doesn't allocate a new vector.

[blegat]

Why does this forces us to modify it in place ? In the example I have written above, they are not modified in place.

[tkoolen]

@blegat, that works fine, but it would allocate about twice as much as it currently does. But see the last paragraph of #211 (comment).

[joaquimg]

I mean that it is super useful to have a single vector with variable indices and another with coefficients. With a struct its better, I think its less natural that two vectors, but it would work fine.
I do not see a lot of user protection in MOI, then I could not see why this specific case is more important.
For instance a vector function in a set with given dimension is not protected, a user could send a vector function in a set of weird dimension. I do not think that a imperfect design at one point should imply bad design somewhere else.I think if we want to protect the user we might need a few other fixes.

[mlubin]

@tkoolen, would an inner constructor on ScalarAffineFunction that validates length(variables) == length(coefficients) address your concerns? (And similarly for other functions.)