[WIP] Scalar affine function reloaded

[matbesancon]

This PR is a first take on https://github.com/jump-dev/MathOptInterface.jl/issues/863

Before we get into yet another scope creep, I think it is reasonable to try this only on SAF for now.

This comes from few observations:

1. A scalar linear function can be viewed as a collection of terms, or as a pair of collections (coefficients, variables). There is no right way to represent it
2. Most (all?) solvers need the second representation and end up rebuilding the two vectors.
3. MOI may be passed a collection of terms (it may make more sense when parsing JuMP expressions) or the tuple. Having an alternative representation can avoid allocating memory twice (once to convert to SAF, one to convert back to two vectors).

I started by adding the second representation ScalarAffineColumnFunction and realized most of the code could be factorized with an abstract type AbstractScalarAffineFunction{T}.

Still to-do:

1. Bridge from one to the other: not sure this is needed in addition to conversion?
2. Documentation update on some points
3. Tests

[odow]

A bridge would be good. Then solvers could, if they choose, drop support for ScalarAffineFunction and use this one instead. If it turns out to be much better, then we could transition to JuMP making these instead.

So I guess my wishlist is also: benchmarks to see the difference of using this.

[mlubin]

Agreed, benchmarks should drive this change.

If it turns out to be much better, then why keep the old format?

[matbesancon]

If it turns out to be much better, then why keep the old format?

this could be a longer-term goal. I agree that a bridge will be a first way to start a replacement

[blegat]

We could also have

struct GenericScalarAffineFunction{T, VT<:AbstractVector{MOI.ScalarAffineTerm{T}}}
    terms::VT
    constant::T
end
const ScalarAffineFunction{T} = GenericScalarAffineFunction{T, Vector{MOI.ScalarAffineTerm{T}}}
struct ZipTermVector{T} <: AbstractVector{MOI.ScalarAffineTerm{T}}
    coefficients::Vector{T}
    variables::Vector{MOI.VariableIndex}
end

If ZipTermVector implements the AbstractVector API, then most of the code should work with both types of ScalarAffineFunction while allowing solver to directly pick the vector of coefficients if the right type of vector of terms is used. This would close https://github.com/jump-dev/MathOptInterface.jl/issues/525

[matbesancon]

@blegat's design proposal seems to fit the needs of the PR and would result in less changes, I'll change things accordingly. The only awkward thing is that solvers will dispatch on the subtype VT in:

GenericScalarAffineFunction{T, VT}

[blegat]

You can still define const ScalarAffineColumnFunction{T} = GenericScalarAffineFunction{T, ...} to facilitates dispatch

[matbesancon]

I'll let you appreciate the awfully cryptic error messages:

ERROR: LoadError: LoadError: cannot assign a value to variable Core.Integer from module MathOptInterface
Stacktrace:
 [1] top-level scope at /home/mbesancon/julia_projects/MathOptInterface.jl/src/sets.jl:667
 [2] include(::Function, ::Module, ::String) at ./Base.jl:380
 [3] include at ./Base.jl:368 [inlined]
 [4] include(::String) at /home/mbesancon/julia_projects/MathOptInterface.jl/src/MathOptInterface.jl:1
 [5] top-level scope at /home/mbesancon/julia_projects/MathOptInterface.jl/src/MathOptInterface.jl:136
 [6] include(::Function, ::Module, ::String) at ./Base.jl:380
 [7] include(::Module, ::String) at ./Base.jl:368
 [8] top-level scope at none:2
 [9] eval at ./boot.jl:331 [inlined]
 [10] eval(::Expr) at ./client.jl:467
 [11] top-level scope at ./none:3
in expression starting at /home/mbesancon/julia_projects/MathOptInterface.jl/src/sets.jl:667
in expression starting at /home/mbesancon/julia_projects/MathOptInterface.jl/src/MathOptInterface.jl:136
ERROR: LoadError: Failed to precompile MathOptInterface [b8f27783-ece8-5eb3-8dc8-9495eed66fee] to /home/mbesancon/.julia/compiled/v1.5/MathOptInterface/tyub8_cF1HQ.ji.

[odow]

Presumably it's the use of ::Integer in src/functions.jl which conflicts with the MOI set MOI.Integer. Perhaps just use ::Core.Integer instead?

[matbesancon]

Indeed yes, fixed it and added comments in last commits. I now how more expected failing tests

[matbesancon]

All the failures now are in Bridges, looking like follows:

 [1] top-level scope at /home/mbesancon/julia_projects/MathOptInterface.jl/test/Bridges/lazy_bridge_optimizer.jl:490
 [2] top-level scope at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/Test/src/Test.jl:1115
 [3] top-level scope at /home/mbesancon/julia_projects/MathOptInterface.jl/test/Bridges/lazy_bridge_optimizer.jl:483
 [4] top-level scope at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/Test/src/Test.jl:1190
Interval constraint: Test Failed at /home/mbesancon/julia_projects/MathOptInterface.jl/test/Bridges/lazy_bridge_optimizer.jl:500
  Expression: debug_string(MOIB.debug_supports_constraint, F, S) == MOI.Utilities.replace_acronym("`MOI.ScalarAffineFunction{$(T)}`-in-`MOI.Interval{$(T)}` constraints are not supported and cannot be bridged into supported constrained variables and constraints. See details below:\n [1] constrained variables in `MOI.GreaterThan{$(T)}` are not supported because no added bridge supports bridging it.\n   Cannot add free variables and then constrain them because free variables are bridged but no functionize bridge was added.\n [2] constrained variables in `MOI.LessThan{$(T)}` are not supported because no added bridge supports bridging it.\n   Cannot add free variables and then constrain them because free variables are bridged but no functionize bridge was added.\n [3] constrained variables in `MOI.Interval{$(T)}` are not supported because no added bridge supports bridging it.\n   Cannot add free variables and then constrain them because free variables are bridged but no functionize bridge was added.\n (1) `MOI.ScalarAffineFunction{$(T)}`-in-`MOI.Interval{$(T)}` constraints are not supported because:\n   Cannot use `$(MOIB.Constraint.SplitIntervalBridge{T, MOI.ScalarAffineFunction{T}, MOI.Interval{T}, MOI.GreaterThan{T}, MOI.LessThan{T}})` because:\n   (2) `MOI.ScalarAffineFunction{$(T)}`-in-`MOI.GreaterThan{$(T)}` constraints are not supported\n   (3) `MOI.ScalarAffineFunction{$(T)}`-in-`MOI.LessThan{$(T)}` constraints are not supported\n   Cannot use `$(MOIB.Constraint.ScalarSlackBridge{T, MOI.ScalarAffineFunction{T}, MOI.Interval{T}})` because:\n   [3] constrained variables in `MOI.Interval{$(T)}` are not supported\n (2) `MOI.ScalarAffineFunction{$(T)}`-in-`MOI.GreaterThan{$(T)}` constraints are not supported because:\n   Cannot use `$(MOIB.Constraint.ScalarSlackBridge{T, MOI.ScalarAffineFunction{T}, MOI.GreaterThan{T}})` because:\n   [1] constrained variables in `MOI.GreaterThan{$(T)}` are not supported\n (3) `MOI.ScalarAffineFunction{$(T)}`-in-`MOI.LessThan{$(T)}` constraints are not supported because:\n   Cannot use `$(MOIB.Constraint.ScalarSlackBridge{T, MOI.ScalarAffineFunction{T}, MOI.LessThan{T}})` because:\n   [2] constrained variables in `MOI.LessThan{$(T)}` are not supported\n")
   Evaluated: "`MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}}`-in-`MOI.Interval{Int64}` constraints are not supported and cannot be bridged into supported constrained variables and constraints. See details below:\n [1] constrained variables in `MOI.GreaterThan{Int64}` are not supported because no added bridge supports bridging it.\n   Cannot add free variables and then constrain them because free variables are bridged but no functionize bridge was added.\n [2] constrained variables in `MOI.LessThan{Int64}` are not supported because no added bridge supports bridging it.\n   Cannot add free variables and then constrain them because free variables are bridged but no functionize bridge was added.\n [3] constrained variables in `MOI.Interval{Int64}` are not supported because no added bridge supports bridging it.\n   Cannot add free variables and then constrain them because free variables are bridged but no functionize bridge was added.\n (1) `MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}}`-in-`MOI.Interval{Int64}` constraints are not supported because:\n   Cannot use `MOIB.Constraint.SplitIntervalBridge{Int64,MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}},MOI.Interval{Int64},MOI.GreaterThan{Int64},MOI.LessThan{Int64}}` because:\n   (2) `MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}}`-in-`MOI.GreaterThan{Int64}` constraints are not supported\n   (3) `MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}}`-in-`MOI.LessThan{Int64}` constraints are not supported\n   Cannot use `MOIB.Constraint.ScalarSlackBridge{Int64,MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}},MOI.Interval{Int64}}` because:\n   [3] constrained variables in `MOI.Interval{Int64}` are not supported\n (2) `MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}}`-in-`MOI.GreaterThan{Int64}` constraints are not supported because:\n   Cannot use `MOIB.Constraint.ScalarSlackBridge{Int64,MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}},MOI.GreaterThan{Int64}}` because:\n   [1] constrained variables in `MOI.GreaterThan{Int64}` are not supported\n (3) `MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}}`-in-`MOI.LessThan{Int64}` constraints are not supported because:\n   Cannot use `MOIB.Constraint.ScalarSlackBridge{Int64,MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}},MOI.LessThan{Int64}}` because:\n   [2] constrained variables in `MOI.LessThan{Int64}` are not supported\n" == "`MOI.ScalarAffineFunction{Int64}`-in-`MOI.Interval{Int64}` constraints are not supported and cannot be bridged into supported constrained variables and constraints. See details below:\n [1] constrained variables in `MOI.GreaterThan{Int64}` are not supported because no added bridge supports bridging it.\n   Cannot add free variables and then constrain them because free variables are bridged but no functionize bridge was added.\n [2] constrained variables in `MOI.LessThan{Int64}` are not supported because no added bridge supports bridging it.\n   Cannot add free variables and then constrain them because free variables are bridged but no functionize bridge was added.\n [3] constrained variables in `MOI.Interval{Int64}` are not supported because no added bridge supports bridging it.\n   Cannot add free variables and then constrain them because free variables are bridged but no functionize bridge was added.\n (1) `MOI.ScalarAffineFunction{Int64}`-in-`MOI.Interval{Int64}` constraints are not supported because:\n   Cannot use `MOIB.Constraint.SplitIntervalBridge{Int64,MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}},MOI.Interval{Int64},MOI.GreaterThan{Int64},MOI.LessThan{Int64}}` because:\n   (2) `MOI.ScalarAffineFunction{Int64}`-in-`MOI.GreaterThan{Int64}` constraints are not supported\n   (3) `MOI.ScalarAffineFunction{Int64}`-in-`MOI.LessThan{Int64}` constraints are not supported\n   Cannot use `MOIB.Constraint.ScalarSlackBridge{Int64,MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}},MOI.Interval{Int64}}` because:\n   [3] constrained variables in `MOI.Interval{Int64}` are not supported\n (2) `MOI.ScalarAffineFunction{Int64}`-in-`MOI.GreaterThan{Int64}` constraints are not supported because:\n   Cannot use `MOIB.Constraint.ScalarSlackBridge{Int64,MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}},MOI.GreaterThan{Int64}}` because:\n   [1] constrained variables in `MOI.GreaterThan{Int64}` are not supported\n (3) `MOI.ScalarAffineFunction{Int64}`-in-`MOI.LessThan{Int64}` constraints are not supported because:\n   Cannot use `MOIB.Constraint.ScalarSlackBridge{Int64,MOI.GenericScalarAffineFunction{Int64,Array{MOI.ScalarAffineTerm{Int64},1}},MOI.LessThan{Int64}}` because:\n   [2] constrained variables in `MOI.LessThan{Int64}` are not supported\n"

[odow]

The bridge errors are just printing.

More serious is this

Testing /home/runner/work/MathOptInterface.jl/MathOptInterface.jl/test/Bridges/Constraint/slack.jl
311
Scalar slack: Error During Test at /home/runner/work/MathOptInterface.jl/MathOptInterface.jl/test/Bridges/Constraint/slack.jl:14
312
  Got exception outside of a @test
313
  UndefVarError: VT not defined
314
  Stacktrace:
315
   [1] MathOptInterface.GenericScalarAffineFunction(::VT, ::Float64) where VT<:Array{MathOptInterface.ScalarAffineTerm{Float64},1} at /home/runner/work/MathOptInterface.jl/MathOptInterface.jl/src/functions.jl:80
316
   [2] modify_function at /home/runner/work/MathOptInterface.jl/MathOptInterface.jl/src/Utilities/functions.jl:973 [inlined]
317
   [3] _modifyconstr at /home/runner/work/MathOptInterface.jl/MathOptInterface.jl/src/Utilities/model.jl:68 [inlined]
318
   [4] _modify(::Array{Tuple{MathOptInterface.ConstraintIndex{MathOptInterface.GenericScalarAffineFunction{Float64,Array{MathOptInterface.ScalarAffineTerm{Float64},1}},MathOptInterface.EqualTo{Float64}},MathOptInterface.GenericScalarAffineFunction{Float64,Array{MathOptInterface.ScalarAffineTerm{Float64},1}},MathOptInterface.EqualTo{Float64}},1}, ::MathOptInterface.ConstraintIndex{MathOptInterface.GenericScalarAffineFunction{Float64,Array{MathOptInterface.ScalarAffineTerm{Float64},1}},MathOptInterface.EqualTo{Float64}}, ::Int64, ::MathOptInterface.ScalarConstantChange{Float64}) at /home/runner/work/MathOptInterface.jl/MathOptInterface.jl/src/Utilities/model.jl:76

[matbesancon]

Using type printing for tests is not robust.

Julia 1.6:

julia> MOI.ScalarAffineFunction{Float64}
MathOptInterface.GenericScalarAffineFunction{Float64, Vector{MathOptInterface.ScalarAffineTerm{Float64}}}

Julia 1.5:

julia> MOI.ScalarAffineFunction{Float64}
MathOptInterface.GenericScalarAffineFunction{Float64,Array{MathOptInterface.ScalarAffineTerm{Float64},1}}

The hacky path:tm: would be to override show for the type

[matbesancon]

pinging @blegat, not sure what a good future-proof solution would be

[odow]

You should interpolate the type into the string that is being checked against.

Instead of "MOI.ScalarAffineFunction{Float64}", use "$(MOI.ScalarAffineFunction{Float64})".

[matbesancon]

the issue is that string interpolation with $ replaces MOI with MathOptInterface

[odow]

Looks like you need to update these sorts of lines https://github.com/jump-dev/MathOptInterface.jl/blob/e0f8b05682d98ae0d45812e1ca7bb6183053c148/test/Bridges/lazy_bridge_optimizer.jl#L352

[matbesancon]

@odow some update when updating these lines, this was a pain because the alias printing behavior changed with julia 1.6, so we could accommodate the string tests to 1.6 or to 1.0

[blegat]

Note that it needs to be exported for the alias to work, see https://github.com/jump-dev/MathOptInterface.jl/pull/1521#issuecomment-896787043

[matbesancon]

@blegat that's not helping our case if we don't want to export things and still keep the SAF alias correctly? In case getting this alias to work is troublesome, this might mean we would prefer making this (slightly) breaking change before a 1.0

[matbesancon]

@odow related to the 1.x label

[odow]

I think we can count printing changes as non-breaking (that's what Julia has done between minor versions), so I'm not worried about that. Keeping this as a 1.x item.

[odow]

What's the status of this? Potentially close as stale? I think there's still appetite for exploring alternative representations, but the cost of transitioning is high.

[matbesancon]

we can close as stale, I do think there is a pain point in having to unpack inner structures into flat (coefficient, indices) structs but I don't have the bandwidth for it right now

[odow]

I do think there is a pain point in having to unpack inner structures into flat

Yeah. One lesson I think we can learn from MOI is that vector-of-structs was a bad idea. For a linear function, you want

struct ScalarAffineFunction{T}
    constant::T
    terms::Dict{VariableIndex,T}
end

# or

struct ScalarAffineFunction{T}
    constant::T
    variables::Vector{VariableIndex}
    coefficients::Vector{T}
end

I get that iterating over a Vector{ScalarAffineTerm{T}} was easier, but it's not that much harder to iterate of the two vectors, and you could even create an iterator type that made it simple. But having access to the vector of coefficients directly is useful.

[odow]

Closing as stale. Will leave #863 open.