3
$\begingroup$

I have an undirected network with capacitated links/edges. Between some nodes unsplittable traffic has to be routed. All demands and capacities are known, but it is uncertain if all flows can be routed without capacity violations.

This problem seemed to be similar the classical unsplittable flow problem (UFP). However, I am not really interested in routing as many flows as possible. I rather want a solution where all flows are routed without violations or I will recompute different demands and try again.

Since this is just part of a bigger heuristic I am building, I was looking for fast and easy to understand algorithms that I could implement. I read some papers and presentations on the UFP (e.g. this). Unfortunately, in the algorithm description (slide 22) it doesn't descirbe how the possible paths are searched for and how the flow is routed.

I would be thankful for some fast and simple algorithms to solve my problem. If the UFP is not as similar as I thought, I am also glad to learn about new more applicable problem models.

I also thought about calculating the shortest paths using Dijkstra's algorithm while also updating the capacities. But that might not always find solutions, even if it is a feasible problem, i.e. when the order of the routed flows is of matter. Also, I'm not sure if this is a very efficient way.

$\endgroup$
1
$\begingroup$

The easiest algorithm to implement will probably be to use integer linear programming, and then use an off-the-shelf ILP solver. I would suggest starting with that and seeing if it is efficient enough, and only dive into the literature if ILP does not meet your needs.

One formulation as ILP could go something like this. For each edge $e$ and each source $s$ you have a variable $f_{e,s}$ that indicates how much flow from source $s$ goes through edge $e$. You'll have a constraint saying that $\sum_s f_{e,s}$ has to be at least the demand and at most the capacity, for each edge $e$. Also, you'll have a constraint representing conservation of flow.

Finally, to encode the unsplittable flow condition, for each edge $(v,w) \in E$ and each source $s$, add a variable $x_{v,w,s}$ that is $1$ if the flow from $s$ enters $v$ and goes next to $w$, or 0 otherwise. To ensure that no flow splits, you'll have a constraint $\sum_w x_{v,w,s} \le 1$ for each $v,s$ and a constraint $f_{(v,w),s} \le K \cdot x_{v,w,s}$, where $K$ is a huge constant.

This should be relatively easy to implement. You can formulate some code to produce the right ILP system in an hour or two, and then use an off-the-shelf ILP solver. Therefore, you should be able to very quickly experiment with this approach and see whether it meets your needs or not, before diving into the research literature on multi-terminal unsplittable flow problems.

$\endgroup$
  • $\begingroup$ I have never worked with something like that. How does it work? What kind of ILP do you recommend and how specifically can I include it into my Java project? (I know what ILP is.) $\endgroup$ – CGFoX Dec 23 '14 at 9:39
  • $\begingroup$ Could I use Gurobi for that? $\endgroup$ – CGFoX Dec 23 '14 at 10:16
  • 1
    $\begingroup$ @CGFoX, you can use any ILP solver you like. To get a rough sense of how well it will work, pretty much any ILP solver should be fine. I've used lp_solve -- it is a simple free solver. There are others that are probably better, but it's probably good enough for a first test. CPLEX has a reputation as a high-quality industrial-strength ILP solver, but it's not free, so I'd suggest starting with a free solver. I don't know much about Gurobi. Java bindings aren't strictly necessary: you can output a text file and run lp_solve on it. $\endgroup$ – D.W. Dec 23 '14 at 12:31
  • $\begingroup$ Hm, writing to file, reading, solving, writing back, reading again sounds like quite an effort + time. The heuristic is supposed to be fast and the ILP might be called several 100000 times. I feel like Java bindings would make the handling easier and improve the speed. Do you have any free recommendations for that? $\endgroup$ – CGFoX Dec 23 '14 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.