How to work with JuMP and Graphs.jl

I try to build a flow model using JuMP and (Meta)Graphs.jl. In particular I fail to index the variables. Here is an MWE:

``````using Graphs
using JuMP

g = SimpleDiGraph(4)
for i in 1:3
end

model = Model()
T = 1:2
@variable(model, x[a in edges(g), t in T], Bin)
@constraint(model, x[Edge 1 => 2, 1] == 1)      # error
@constraint(model, x[(2,3),1] == 1)             # error
``````

I tried several combinations, but always failed. As workaround, I could convert the edges as tuples, e.g.,

``````E = [(src(a), dst(a)) for a in edges(g)]
@variable(model, x[a in E, t in T], Bin)
@constraint(model, f[(2,3),1] == 1)           # works
``````

but canâ€™t I use the edges from `g` directly? Unfortunately, I did not find any examples in which JuMP is used together with objects from (Meta)Graphs.jl. Or is doing this a bad practice at all?

Itâ€™s useful to also show the errors you get.

In that case I think you need to do

``````@constraint(model, x[Edge(1 => 2), 1] == 1)
``````

As far as I know JuMP cannot understand Graphs.jl so you have to give it the numbers. Use `get_prop!` from MetaGraphs.jl for that.

Probably a good resource is GitHub - JuliaGraphs/GraphsOptim.jl: A package for graph optimization algorithms that rely on mathematical programming.
Have a look at the source code to see how they define models.

3 Likes

@filchristou is correct.

Your set is `edges(g)`, so the keys are the elements of that set.

``````julia> using Graphs, JuMP

julia> g = SimpleDiGraph(4)
{4, 0} directed simple Int64 graph

julia> for i in 1:3
end

julia> model = Model();

julia> @variable(model, x[edges(g), 1:2], Bin)
2-dimensional DenseAxisArray{VariableRef,2,...} with index sets:
Dimension 1, Graphs.SimpleGraphs.SimpleEdge{Int64}[Edge 1 => 2, Edge 2 => 3, Edge 3 => 4]
Dimension 2, Base.OneTo(2)
And data, a 3Ă—2 Matrix{VariableRef}:
x[Edge 1 => 2,1]  x[Edge 1 => 2,2]
x[Edge 2 => 3,1]  x[Edge 2 => 3,2]
x[Edge 3 => 4,1]  x[Edge 3 => 4,2]

julia> x[Edge(1 => 2), 1]
x[Edge 1 => 2,1]
``````

Your `Edge 1 => 2` attempt came because Graphs for some reason has overloaded `Base.show` to remove the parenthesesâ€¦

``````julia> Edge(1 => 2)
Edge 1 => 2
``````

JuMP doesâ€™t now about Graphs.jl, so we just print what we get given.

1 Like