Support "nonscalar" variables (like complex numbers, intervals, sequences of intervals)?

[dourouc05]

For now, MOI only supports scalar variables, i.e. real numbers (or subsets thereof). Complex numbers can be implemented as a pair of real numbers, as in https://github.com/jump-dev/ComplexOptInterface.jl. For constraint programming, I would need to represent intervals (i.e. a pair of integer values: the beginning and the end of the interval) and sequences of intervals (defined based on a series of intervals), but also graphs. This kind of needs spans several engines:

• CPLEX has specific types for these variables, and an interval cannot be constructed from other variables. In OPL (their modelling language): interval (also described more generally: https://www.ibm.com/support/knowledgecenter/SSSA5P_20.1.0/ilog.odms.cpo.help/refcppcpoptimizer/html/interval_variables.html) and sequence (high-level overview: https://www.ibm.com/support/knowledgecenter/SSSA5P_20.1.0/ilog.odms.cpo.help/refcppcpoptimizer/html/constraints_groups.html).
• OscaR is another CP engine that has similar requirements. This one has sequences (https://bitbucket.org/oscarlib/oscar/src/dev/oscar-cp/src/main/scala/oscar/cp/core/variables/CPSeqVar.scala and subclasses CPHeadSeqVar, CPInsertSeqVar), but also graphs (https://bitbucket.org/oscarlib/oscar/src/dev/oscar-cp/src/main/scala/oscar/cp/core/variables/CPGraphVar.scala).
• Gecode has set variables (https://www.gecode.org/doc-latest/MPG.pdf, Chapter 5).

How could this kind of variables fit into MOI? (Or an extension to MOI.) Typical functions cannot be applied on this kind of object: two intervals cannot really be summed up, or be greater than some constant, for instance.

Maybe renaming SingleVariable as SingleScalarVariable/SingleRealVariable (and so on for the other related objects)? This would leave space for something like SingleIntervalVariable, SingleSequenceVariable (and vectors), etc., but also SingleComplexVariable.

In a way, it could also solve some problems with supports_constraint: many CP constraints only make sense for integer variables (e.g., an array index), others are generalisable but are not always implemented as such (like counting values equal to something). With a SingleIntegerVariable, supports_constraint could directly check for the type of variables.

[blegat]

Here is another case where it would be useful to know the type of the variable.
Cbc also has issues when the variables are not binary in a SOS constraint: jump-dev/Cbc.jl#151

[dourouc05]

After giving it some thoughts, here is what I propose to implement for this, in two parts.

Variable traits

A system similar to Holy traits for variables, so that you can easily query if a variable is binary or has bounds, for instance. That would mean a series of functions like is_binary(::ModelLike, ::VariableIndex)::Bool, is_integer::Bool, is_real::Bool, has_lower_bound::Bool (most of them are already available in JuMP: this would just mean moving some code from JuMP to MOI). A naïve implementation would be to look through the SingleVariable-in-Whatever constraints in the model, but storing a large series of Boolean values could probably be optimised a lot more than this. This would be helpful for Cbc, as @blegat mentioned, but also for CP, as I needed a way to perform dispatch on whether a variable is integer to output models to FlatZinc (https://github.com/dourouc05/ConstraintProgrammingExtensions.jl/blob/master/src/FlatZinc/FlatZinc.jl#L494-L508, for instance).

Apart from moving some code from JuMP to MOI, I don't think that further changes are really required. It's nothing fundamental, it's more about giving easier access to some information (so that people can decide to perform more type checks or interesting dispatch later on).

In the near future, this could be extended to support DCP in JuMP, with vexity, monotonicity, sign.

Composite variable indices

A new notion: composite variables (or any other name), CompositeVariableIndex, let's say, that is, one object that holds several highly-related variables (e.g., the real and imaginary parts of a complex number, the beginning and the end of a time interval). Each of those "subvariables" would have their own VariableIndex, so that they can be accessed easily. With this mechanism, it would not be possible to have ComplexVariable-in-LessThan or IntervalVariable-in-LessThan, unless a solver specifically supports this kind of constraint, without any relationship to Single-Variable-in-LessThan (this is a reason why traits would not really be helpful in this case). When the user wants to access some parts of the composite variable, they would have access to one of those subvariables: you could add a constraint on the real part of a complex number, for instance.

More technically, I would implement this with an abstract CompositeVariableIndex that could be inherited from to create ComplexVariableIndex, IntervalVariableIndex, GraphVariableIndex, and more if needed (probably none of them in MOI as of now). These could look like this:

mutable struct ComplexVariableIndex <: CompositeVariableIndex
  re::VariableIndex
  im::VariableIndex
end

mutable struct IntervalVariableIndex<: CompositeVariableIndex
  start_of::VariableIndex
  end_of::VariableIndex
end

mutable struct GraphVariableIndex<: CompositeVariableIndex
  edges::Dict{Tuple{Int, Int}, VariableIndex}
  
  function GraphVariableIndex(n_vertices::Int)
    return new(Dict((i, j) => new_bin_var for i in 1:n_vertices, j in 1:n_vertices if i != j))
  end
end

Syntactically, from the point of view of JuMP, this could just be some extension of the @variable syntax: along with @variable(model, x, Bin) and @variable(model, x[1:2, 1:2], PSD), you would have @variable(model, x, Complex), @variable(model, x, Interval), or @variable(model, x[...], Graph(5)). I sense that the graph part will be more troublesome, as computing the dimension is not trivial, and it would really be useful for users if they could just ignore that part. Given the existing possibilities, @variable(model, x[i=1:n_vertices, j=1:n_vertices; i != j], Graph) and @variable(m, z1[(i, j) in s]) (s being a list of tuples) could already be enough.

Then, constraints could be written in a specific way with these new compound types. You could define affine expressions based on complex variables or intervals: ScalarAffineExpression{Float64, ComplexVariableIndex}-in-EqualTo{Complex{Float64}}.

In a way, it would have been more interesting to have Complex{VariableIndex}, but VariableIndex is not a Real subtype. Moreover, there is no notion of time interval in the standard library (Intervals.jl has it, for instance), and there is no unique graph data structure (albeit LightGraphs is almost ubiquitous). This situations forces to create dedicated types for time intervals and graphs.

---

Do you have any opinion on this? Shall I open PRs to discuss more concretely?

[odow]

Is there any reason this needs to happen in MOI directly? My near-term goal is jump-dev/JuMP.jl#2564, so I'm wary of adding lots of new functionality before we get 1.0 finished.

Functions like is_binary don't need to be:

function is_binary(model::MOI.ModelLike, x::MOI.VariableIndex)::Bool
    return MOI.is_valid(
        model, 
        MOI.ConstraintIndex{MOI.SingleVariable,MOI.ZeroOne}(x.value),
    )
end

I can't find the issue, but I suggested something like CompositeVariableIndex before in the context of JuMP. I think it was for interval variables, where

@variable(model, x, ConstraintInterval)

created x.start, x.end and x.length. This is something interesting to consider, but I don't think it needs to be part of MOI in the near-term.

[dourouc05]

Indeed, there is no need to include it in MOI right away, but I prefer to discuss the ideas before doing anything, in case I missed something or if there is a better implementation. Thanks for your input!

By the way, I believe this belongs to https://github.com/dourouc05/ConstraintProgrammingExtensions.jl for now? Or would it be better to have another package to ease inclusion in a future MOI release?

[odow]

Yeah keep adding things to ConstraintProgrammingExtensions for now. Want to give a talk at JuMP-dev about ConstraintProgrammingExtensions? It would be good to generate some wider discussion.

[dourouc05]

I'll submit an abstract for the workshop for sure! I suppose that a standard talk would be the best length for such a topic?

[blegat]

Yes, I would say you would need at least the length of a standard talk

[dourouc05]

OK, thanks a lot!

[odow]

We've made no progress on this, and I don't think we're going to anytime soon. To some extent, we have support for complex numbers, but it still requires adding two real variables. I think these ideas are perhaps best explored in a JuMP extension package.

[odow]

A good example for this would be local solver's list and set variable types: https://www.localsolver.com/docs/last/modelingfeatures/collectionvariables.html

I haven't worked through the details, but perhaps x in List(10) an x in Partition() could work to construct a list variable and a partition constraint. It's pretty clunky, and it depends on x in Partition() being able to work out that x is exactly a list variable. We couldn't support any old VectorOfVariables in Partition.

[odow]

I wonder if we should close this issue as out-of-scope. Supporting anything other than VariableIndex is a huge change, and we have the potential to either develop things as a JuMP extension, or to (ab)use the MOI definitions to support things like x in Set implies special stuff about x.

The most promising thing from the title is complex numbers. But we don't have any solvers at the MOI level requiring complex numbers, and we've shown that it can work at the JuMP level.

[blegat]

Yes, I'm unsure that we need it, we've also been able to have bridge act differently depending on properties of a variable by checking whether they are constrained to belong to some set in final_touch.

[odow]

To clarify, the closing of this: I talked to @dourouc05 yesterday, and we agreed that adding something other than VariableIndex is a big change.

The current suggestion for "interval" variables would be something like x[1:2] in Interval(), and then some support in JuMP to convert that into a struct start::VariableRef; finish::VariableRef.