# How to Handle Multiple Edges in a Routing Problem Using JuMP?
**URL:** https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226
**Category:** Optimization (Mathematical)
**Tags:** question, jump, graph
**Created:** [September 25, 2023, 2:09pm UTC](https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226 "2023-09-25T14:09:53Z")
**Posts on this page:** 9
**Page:** 1
### Author:  [@F\_A](https://discourse.julialang.org/u/F_A)
#### Post date: [September 25, 2023, 2:09pm UTC](https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226/1 "2023-09-25T14:09:53Z")
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:
```julia
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?
```julia
@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!
---
### Author:  [@slwu89](https://discourse.julialang.org/u/slwu89)
#### Post date: [September 25, 2023, 6:26pm UTC](https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226/2 "2023-09-25T18:26:15Z")
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.
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [September 25, 2023, 7:50pm UTC](https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226/3 "2023-09-25T19:50:59Z")
> [@F\_A](#):
>
> 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` ?
You need a separate binary variable for each edge, not each pair of origin-destination nodes.
---
### Author:  [@F\_A](https://discourse.julialang.org/u/F_A)
#### Post date: [September 26, 2023, 8:03am UTC](https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226/4 "2023-09-26T08:03:09Z")
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.
---
### Author:  [@slwu89](https://discourse.julialang.org/u/slwu89)
#### Post date: [September 26, 2023, 3:10pm UTC](https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226/5 "2023-09-26T15:10:46Z")
At the risk of suggesting something too niche, I’ll point out that [Catlab.jl](https://github.com/AlgebraicJulia/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).
```julia
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)
```
---
### Author:  [@F\_A](https://discourse.julialang.org/u/F_A)
#### Post date: [September 26, 2023, 7:06pm UTC](https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226/6 "2023-09-26T19:06:29Z")
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.
---
### Author:  [@slwu89](https://discourse.julialang.org/u/slwu89)
#### Post date: [October 29, 2023, 9:16pm UTC](https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226/7 "2023-10-29T21:16:46Z")
@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.
---
### Author:  [@F\_A](https://discourse.julialang.org/u/F_A)
#### Post date: [October 30, 2023, 8:06am UTC](https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226/8 "2023-10-30T08:06:29Z")
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!
---
### Author:  [@slwu89](https://discourse.julialang.org/u/slwu89)
#### Post date: [October 30, 2023, 9:44pm UTC](https://discourse.julialang.org/t/how-to-handle-multiple-edges-in-a-routing-problem-using-jump/104226/9 "2023-10-30T21:44:33Z")
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.