How to work with JuMP and Graphs.jl

Specific Domains Optimization (Mathematical)
1

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
    add_edge!(g, i, i+1)
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?

2

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
3

@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
           add_edge!(g, i, i+1)
       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