juliaopt / mathoptinterfacebridges.jl Goto Github PK

jump-dev/MathOptInterface.jl#140

Should this repository be archived? As I understand, these features have been moved to MOI.Bridges

Currently, the same code is written in ECOS, in SCS, in SDOI and in MOIU/bridge.jl.

It would be good to avoid having this chunk of code copy pasted everywhere. I can see two solution, vote for your preferred one:

• Have an abstract type defined in MOIU like AbstractSolverInstanceWithInstance described in MOIU and have this code for this abstract type only once here 👍
• Have a macro like @redirectinstancemodification solverinstancetype instancefield that returns this code that is duplicated ❤️
• None of them, I like copy paste 👎

This seems related to InstanceManager (see #32 ) so we might have code shared between the two.

MOI methods that add constraints using affine functions build the problem matrix on the side of MILP solvers. The datastructure and the interface to those solvers has a generic part (everything except the compression type used by the matrix).

Should we have this in MOIU ?

related to #5 and jump-dev/Clp.jl#21

Should be instance.

See

https://github.com/JuliaOpt/MathOptInterfaceUtilities.jl/blob/edf384aa6a448126e5924ae7344f0ccc5583d611/test/instancemanager.jl#L153

Probably falls under #61, feel free to close if you think it does.

It would be nice to have a bridge that transforms DualExponentialCone constraints into ExponentialCone constraints for solvers like ECOS which do not support DualExponentialCone but support ExponentialCone.
It seems to me that (u, v, w) belongs to DualExponentialCone if and only if (-v, -u, exp(1) w) belongs to ExponentialCone so it should be rather simple.

It should throw an error if two variables or two constraints are assigned the same (nonempty) name. Currently it ignores this check and lookup by name returns the last variable that was assigned the given name:
https://github.com/JuliaOpt/MathOptInterfaceUtilities.jl/blob/d9d1c4f20b1667e440b2a54831fefe8a117e433a/src/instance.jl#L130-L133
https://github.com/JuliaOpt/MathOptInterfaceUtilities.jl/blob/d9d1c4f20b1667e440b2a54831fefe8a117e433a/src/instance.jl#L140

MOIT/instance.jl should test this case.

So far we've been imagining that JuMP would be responsible for keeping the instance and the solver instance in sync, e.g.:
https://github.com/JuliaOpt/JuMP.jl/blob/d3e40d9a047c2da3b9242d57fb55dec1fba9301d/src/quadexpr.jl#L154
jump-dev/JuMP.jl#1069

I propose to change the design a bit, and move the syncing logic to the MOI level. Let's imagine we have an InstanceManager that stores a standalone instance and optionally a solver instance. It would implement a variant of the MOI interface with well-defined semantics for when the solver instance is kept in sync with the standalone instance. This would be:

• easier to test as an MOI-level object rather than as part of JuMP.
• usable directly without JuMP (which I believe addresses @IssamT's comments in jump-dev/MathOptInterface.jl#106)

One point that's not clear (which we'd need to resolve anyway) is whether to query the standalone instance or the solver instance for certain attributes. This comes up also in bridges: jump-dev/MathOptInterface.jl#169.

@odow

In

https://github.com/JuliaOpt/MathOptInterfaceUtilities.jl/blob/c5b5c4bcae650a141101fb1e16d459c84e582bb9/src/instancemanager.jl#L359-L364

typeof(index) is used for canget, even though a concrete index is available. That seems too strict. It may be the case that you can get an attribute for certain indices, but not all.

I started implementing support for quadratic expressions in JuMP and saw that MOIU only supports affine objectives. What is needed to support quadratic objectives?

If you replace, e.g.,
https://github.com/JuliaOpt/MathOptInterfaceUtilities.jl/blob/249abf790eb75e673ee346e2952f3a6149e92254/test/instance.jl#L112
with

vc3 = MOI.addconstraint!(m, v[3], MOI.EqualTo(0.0))

the test fails with an ambiguity warning:

  Got an exception of type MethodError outside of a @test
  MethodError: MathOptInterface.addconstraint!(::Instance{Float64}, ::MathOptInterface.VariableReference, ::MathOptInterface.EqualTo{Float64}) is ambiguous. Candidates:
    addconstraint!(m::MathOptInterfaceUtilities.AbstractInstance, f::F, s::S) where {F, S} in MathOptInterfaceUtilities at /home/mlubin/.julia/v0.6/MathOptInterfaceUtilities/src/instance.jl:141
    addconstraint!(m::MathOptInterface.AbstractInstance, v::MathOptInterface.VariableReference, set) in MathOptInterface at /home/mlubin/.julia/v0.6/MathOptInterface/src/constraints.jl:23
  Possible fix, define
    addconstraint!(::MathOptInterfaceUtilities.AbstractInstance, ::MathOptInterface.VariableReference, ::Any)

Solvers often support a specific set of (function, set) constraints but other constraint can be transformed into these pairs.
Therefore, different wrappers usually need to develop the same transformation without sharing code. Having these transformation in addition to the rest makes the wrapper code significantly more complicated (even more if it want to return ListOfConstraints, ... accurately).
Sometimes, we would also like to add the support of a (function, set) pair to a solver since we know to transform them into other constraints but we do not want to patch every solver since it would take time and our new constraint may be application specific and not of broad interest.

I think that these uses cases could be easy to solve if the following macro existed:

@bridge Name SomeFunction SomeSet SomeBridge

The macro would create an instance bridge Name <: AbstractSolverInstance such that Name(instance) creates an instance that supports all constraints supported by instance plus (SomeFunction, SomeSet).
The macro would basically create

struct Name{InstanceType}
    instance::InstanceType
    bridges::Vector{SomeBridge}
end

I have already created some bridges in SDOI and it works quite well. The macro does not exist yet though so I had to complicate the wrapper interface to add the bridges::Vector{SomeBridge} inside the wrapper structure, ...
Once the macro is created, this would allow to make SDOI a lot simpler.

Some examples of useful bridges:

• AbstractVectorFunction in PositiveSemidefiniteConeSquare, see jump-dev/JuMP.jl#1125
• AbstractVectorFunction in LogDetCone, i.e. log det(X) <= t
• AbstractVectorFunction in DetRootnCone, i.e. det(X) <= t^n

http://www.juliaopt.org/MathOptInterface.jl/latest/apireference.html#MathOptInterface.ListOfConstraintReferences
This appears to be missing in the interface to Instance

As introduced in #48 (comment), we can distinguish layers of a composition of MOI instances as 1-IO, 2-IO or ∞-IO.
The InstanceManager, plays a central role as it has 1-I and ∞-O. This allows to make 1-IO layers and ∞-IO layers to be used together as follows :

All 1-IO ( InstanceManager ( All ∞-IO ( Solver ) ) )

One question remains : What should we do if there are 2-IO intermediate layers ?

• Scenario 1 : There are none.
• Scenario 2 : Make the InstanceManager implement 2-I so that we can do

All 1-IO ( InstanceManager ( All 2-IO ( InstanceManager ( All ∞-IO ( Solver ) ) ) ) )

• Scenario 2 : Make all solvers implement 2-I so that we can do

All 1-IO ( InstanceManager ( All ∞-IO ( All 2-IO ( Solver ) ) ) )

• Scenario 3 : Make all 1-IO implement 2-IO so that we can do

All 1-IO and 2-IO ( InstanceManager ( All ∞-IO ( Solver ) ) )

So I'm confused about what data structure solvers should use to store their models. Am I meant to be using MOIU? Because JuMP is using it. So it doesn't seem like there should be three copies of the model.

There is also things like: https://github.com/JuliaOpt/MathOptInterfaceUtilities.jl/blob/master/src/instance.jl#L47
But it's not apparent to me that all solvers will want to increment their variable references like that (maybe I support normal variables, and some other kind of variables, and I want to make normal variables even numbered, and weird variables odd numbered so I have a mod operation to check rather than some lookup).

I almost think we should write the solvers a few different ways. Check which ideas work well. Then consider abstracting into some instance type.

The duals won't work for this one though since the dual of ScalarQuadraticFunction-in-LessThan is just a scalar (see jump-dev/MathOptInterface.jl#43), we loose information in comparison with the vector dual of the SOC

The test here should pass for MOIU's instance.

We could have some docs, it is getting harder to understand all that the macro does.

It would be nice to have a bridge that transforms RotatedSecondOrderCone constraints into SecondOrderCone constraints for solvers like SCS which do not support RotatedSecondOrderCone but support SecondOrderCone.
The transformation can be found at page 104 of [Ben-Tal, Nemirovski; 2001; Lectures on Modern Convex Optimization].

jump-dev/MathOptInterface.jl#190
JuliaOpt/MathOptInterfaceTests.jl#37
May also want to wait for jump-dev/MathOptInterface.jl#189 (comment)

See jump-dev/MathOptInterface.jl#213 (comment)

Duals will work with the definition of dual of jump-dev/MathOptInterface.jl#43

Because of

https://github.com/JuliaOpt/MathOptInterfaceUtilities.jl/blob/532ebec78b8b8e35dbf7e7443ddcdb663ff279cf/src/model.jl#L225-L231

and
https://github.com/JuliaOpt/MathOptInterfaceUtilities.jl/blob/532ebec78b8b8e35dbf7e7443ddcdb663ff279cf/src/model.jl#L171

you can set a quadratic objective, ask if you can get a SingleVariable objective (why yes you can!) and then when you call get with ObjectiveFunction{SingleVariable} you receive a ScalarQuadraticFunction.

By the way, I was expecting this to be implemented with three different fields, not just one field with Union type; I guess this is a temporary solution?

In the instance manager, attributes are typically set in both the solver instance and the standalone instance. In automatic mode, they must be set in both, because the solver could be emptied at any time. This means that the standalone instance needs to support all the attributes that the user might want to set on the solver instance. We don't know ahead of time which attributes these are going to be, and they might not be defined in MOI. This points in the direction of having an instance that supports arbitrary attributes, otherwise the usability of the instance manager (and therefore JuMP) is going to be severely restricted.

If we do this, we should consider addressing jump-dev/MathOptInterface.jl#31 so that the container type to store attribute values can be inferred from the attribute itself. The performance considerations are closely related to the discussion in jump-dev/JuMP.jl#1152.

When remove a variable, should we update every function to remove the variable ?

Following up on the discussion at f8667f2. It should be seen as an unsafe operation to store an Int64 when a more specific index type could be used instead. It's unsafe because it disregards type information and easily leads to unintended behavior like #41. Performance is not a good reason to do unsafe things unless you have benchmarks to show otherwise.

See the following benchmark:

using BenchmarkTools

struct Index{T}
    value::Int
end

function f1()
    d = Dict{Index, Float64}()
    for k in 1:1000
        d[Index{String}(k)] = 2.0*k
    end
    s = 0.0
    for k in 1:1000
        s += d[Index{String}(k)]
    end
    return s
end

function f2()
    d = Dict{Index{String}, Float64}()
    for k in 1:1000
        d[Index{String}(k)] = 2.0*k
    end
    s = 0.0
    for k in 1:1000
        s += d[Index{String}(k)]
    end
    return s
end

@btime f1()
@btime f2()

On a recent Julia 0.7 I get:

  159.473 μs (3018 allocations: 139.22 KiB) # f1
  141.097 μs (2926 allocations: 137.78 KiB) # f2

I don't see this as a significant performance hit.

http://www.juliaopt.org/MathOptInterface.jl/latest/apireference.html#MathOptInterface.ListOfVariableReferences

Need this for InstanceManager, and don't see and easy way to add it myself.

Shouldn't we add copying in this function?
This is related to the issue jump-dev/MathOptInterface.jl#67

function _addconstraint!{F, S}(constrs::Vector{Tuple{CR{F, S}, F, S}}, cr::CR, f::F, s::S)
    push!(constrs, (cr, f, s))
    length(constrs)
end

Is it a good idea to create a documentation for this package using Documenter or is it overkill and the README is enough. I feel like it's not overkill and it would allow to automatically transform the docstrings into HTML.

Related : @tkoolen reported in jump-dev/MathOptInterface.jl#209 that "Document the features of MOIU properly (took some time to even figure out what the package was meant for)".

As discussed in jump-dev/JuMP.jl#1152 and in #56 (comment), we should have something that helps instance-without-optimize! support arbitrary constraints, let's call it UniversalFallback.
It can be a lot simpler than bridges since UniversalFallback will not implement optimize! so whatever is the internal instance, optimize! will not be called. This means that the internal instance does not have to contain the full instance, part of the constraints (e.g. the one that it does not support) can be stored outside without the need to transform them into supported constraints as it is the case with bridges.
It could be like

struct UniversalFallback{IT}
    instance::IT
    constraints::Dict{Tuple{DataType, DataType}, Vector}
    attributes::Dict{AbstractInstanceAttribute}
    varattr::Dict{AbstractVariableAttribute, Dict{MOI.VariableIndex}}
    conattr::Dict{AbstracConstraintAttribute, Dict{MOI.ConstraintIndex}}
end

For every MOI functions, the universal fallback try to see if instance supports it. If it does not, it stores it in its dictionaries. The performance of the different ways to store it has be analysed by @rdeits in jump-dev/JuMP.jl#1152

The advantage of the UniversalFallback is that it allows an instance to still support every possible attributes and constraints while still making sure that the most important ones are as efficient as they could be.

I am open to bikeshedding on the name UniversalFallback :-P

Note : it fixes #61