[RFC] supports_constrained_variable

[blegat]

We had a talk with @odow and @mlubin about constrained variables, here is what we came up with:

Currently, there is no way to differentiate whether a constrained variable can be added or whether constraint can be added on existing variables.
However,

• solvers such as SDPNAL, CSDP, SDPA can create constrained variables in Nonnegatives or PSD but cannot create VectorOfVariables-in-Nonnegatives or PSD constraints
• SDPT3 can create constrained variables in Nonnegatives, SecondOrderCone or PSD but cannot create VectorOfVariables-in-Nonnegatives, SecondOrderCone or PSD constraints
• Mosek can create constrained variables in PSD but cannot create VectorOfVariables-in-PSD constraints
• SDPNAL can create SingleVariable-in-Interval constraints but cannot create constrained variables in Interval (as free variables are not supported). The SingleVariable-in-Interval need to be added on Nonnegatives or PSD variables.

Because of these issues, if you call MOI.add_constrained_variable(optimizer::LazyBridgeOptimizer{SDPNAL.Optimizer}, MOI.Interval(1.0, 2.0)), the bridges will let the call go through as MOI.supports(::SDPNAL.Optimizer, ::Type{SingleVariable}, ::Type{Interval{Float64}}) is true and then there will be an error.
Another issue is that the user could create constrained variables in PSD and then constrain some of them in SecondOrderCone in a CachingOptimizer. Then when the cache is copied from the cache to Mosek, it might add constrained variables in SecondOrderCone then then the PSD constraint will need to be added as a constraint as some of the variables have already been added. Then it will give an error.

To solve this issue, we can add

supports_constrained_variable(model::ModelLike, S::Type{<:AbstractScalarSet}) = supports_constraint(model, SingleVariable, S)
supports_constrained_variables(model::ModelLike, S::Type{<:AbstractVectorSet}) = supports_constraint(model, VectorOfVariables, S)

so that a solver can override it if it's not the same.

Then in LazyBridgeOptimizer, supports_constrained_variable will be used instead of supports_constraint when appropriate.
And in copy_to, we need to first add as constrained variables the set that are supported as constrained variables but not as constraint.
For the rest of the set, we could compute, for each set type, the difference between the bridging cost of adding constrained variables vs the bridging cost of adding constraints.
Then the choice of adding which constraint as constrained variables or constraint on free variables can be modeled as a weighted set cover which is NP-hard.
But we could simply order the set types with the cost and use this order as a priority without worrying about the overlapping patterns and that would be cheap.
We just need to add model attributes:

# Cost of bridging constrained variable in S
struct BridgingCost{S} <: AbstractModelAttributes
end
# Cost of bridging F-in-S constraints
struct BridgingCost{F, S} <: AbstractModelAttributes
end

that can be queried from copy_to with default fallbacks:

get(::ModelLike, ::BridgingCost{S}) where {S<:AbstractSet} = MOI.supports_constrained_variable(S) ? 0.0 : Inf
get(::ModelLike, ::BridgingCost{F, S}) where {F<:AbstractFunction, S<:AbstractSet} = MOI.supports_constraint(F, S) ? 0.0 : Inf

that are overwritten by LazyBridgeOptimizer.

[blegat]

What would be the new names for this ? supports_variable_constrained_on_creation and add_variable_constrained_on_creation ?

[mlubin]

add_variable tells you that you are creating a variable, so the on_creation part seems redundant. I think add_constrained_variable is fine as a function name (with supports_add_constrained_variable).
My suggestion, however, is frame the documentation around "was this variable constrained on creation?" instead of "is this a constrained variable?". Any constraint that exists in the model can cause a variable to be constrained, regardless of when it is added.

[blegat]

Closed by #1101 and #1125