How to Handle Multiple Edges in a Routing Problem Using JuMP?

Specific Domains Optimization (Mathematical)
, ,
1

Hi all,

I have a multiple edge graph and I want to solve a routing problem on that. I was wondering how to define a binary variables that accounts for all possible edges that exist between let’s say node i to node j.

I have defined a binary variable x as follows:

x_sets = [(i, j, p, d) for (p, d) in PD for (i, j) in links_pd[(p, d)]]
@variable(model, x[x_sets] >= 0, Bin)

that take a value of one if driver d serve passenger p on link (i,j), where PD is a possible pairs od driver-passenger and links_pd is a dictionary mapping these pairs to their available edges. The issue is that since for some links we have multiple edges, and all have different cost and time. For instance, we have 4 edges with start node 1 and end node 5, and their times are 3.5,1.2,4.7,4.2, respectively. Is there any way to include all of these within x_sets ?

In the objective function it is also difficult to specify that we have multiple edges. how to model this multiple edges correctly?

 @objective(model, Min, sum(Time_pd[(i, j, p, d)] * x[(i, j, p, d)] for (i, j, p, d) in x_sets) )

Many thanks!

2

I’m not sure if it’s possible to easily represent a directed multi-graph using binary variables, unless you knew for example there could not be more than n edges between any two vertices and you had n binary variables for each of those possible edges.

It sounds like you already know the total possible set of edges, because you are able to define links_pd? If you didn’t, I suppose you could define x as a “matrix” of Int to model the presence of multiple edges between nodes. But because you have links_pd perhaps you can rethink the data structure to be an array of binary variables of length equal to the number of edges in links_pd? This a bit more natural in terms of how we’d represent this kind of graph as a database, as a set of Edge and a set of Vertex, and 2 functions giving the src and tgt vertex associated to each edge.

Hope I didn’t misunderstand anything.

2 Likes
3

You need a separate binary variable for each edge, not each pair of origin-destination nodes.

4

So, there’s no package for somehow automatically handling multiple graphs. Yes, I also thought that the way is to have separate variables. Thank you both @slwu89 and @odow for your thoughts and suggestions.

1 Like
5

At the risk of suggesting something too niche, I’ll point out that Catlab.jl can model complex relational data in this way. Here’s a small example of defining a schema for a directed multi-graph where edges may have a time attribute (the code in the @present macro; you can read Ob as a “table”, Hom as foreign keys, and Attr as a column of a table), and creating a data instance on that schema.

That being said looking back at this, I wonder if you might consider a bipartite graph with multiple edges as a more natural data structure for this data (presumably there’s no driver-driver or passenger-passenger links).

using Catlab, ACSets, Tables

@present DriverPassenger(FreeSchema) begin
    (Vertex,Edge)::Ob
    src::Hom(Edge,Vertex)
    tgt::Hom(Edge,Vertex)    
    TimeAttr::AttrType
    time::Attr(Edge,TimeAttr)
end

@acset_type DriverPassengerData(DriverPassenger, index=[:src,:tgt])

sample_data = @acset DriverPassengerData{Float64} begin
    Vertex=3
    Edge=8
    src=[1,1,1,2,3,1,2,3]
    tgt=[2,2,3,1,2,3,3,1]
    time=rand(8)*10
end

# get the source node of edge 1
sample_data[1,:src]

# get the target node of edge 1
sample_data[1,:tgt]

# get the time of edge 1
sample_data[1,:time]

# get all edges with target node 2
incident(sample_data, 2, :tgt)

# can easily iterate with Tables.jl interface
sample_data_tb = tables(sample_data)

# this is iterable
Tables.rows(sample_data_tb.Edge)
2 Likes
6

Thanks again @slwu89, this library is totally new to me. So, I’ll look into it.
No a bipartite graph won’t be multiple edges, as by multiples edge I want to only look into those cases where the start and end node have the same labels.

7

@F_A just wanted to check if you had any luck with this problem.

Also, somewhat selfishly, I’m a contributor to Catlab/ACSets and I’m interested to see if these data structures can actually help out your use case, but I don’t have enough information about the problem yet to help with more concrete code.

1 Like
8

Hi @slwu89.
Thanks for this library and your help! I read it a little bit but did not get a chance to try it because I had already written everything in Jump, and it turns out that the easier option was to reformulate the model slightly at the end.
Thanks again!

2 Likes
9

I’m glad to hear you got it working!

For what it’s worth, if you are still interested, I’d love to take a look at any sample data you’d be willing to share, to see if acsets can help smooth the connection between data representation and an optimization problem in JuMP.

2 Likes