# Unsplittable flow in capacitated networks

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.

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.
• @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. – D.W. Dec 23 '14 at 12:31