# Splittable and non-splittable flows in the network flow problem

I am working on a multi-commodity flow problem where for a graph $$G=(V, E)$$, some flows are permitted to be split and some flows should strictly follow one path. I have formulated this problem as follows.

Problem Formulation

$$\min \sum_{(i,j) \in E} \sum_{f \in F} c_{ij}^fx^f_{ij}$$

$$\sum_{j \in V}x^f_{ij} - \sum_{j \in V}x_{ji}^f = \begin{cases} d_f &, & i = s_f \\ -d_f&, & i = t_f\\ 0 &,& \text{otherwise} \end{cases}$$ $$x_{ij}^f \ge \begin{cases} 0 & , & f \in S\\ d_f & , & f \in NS\\ \end{cases} \quad \forall (i, j) \in E$$ $$\sum_{i,j \in E} x_{ij}^f \le u_{ij}$$

Where $$d_f$$ is the demand for flow $$f$$. $$S$$ is the set of flows that are permitted to be split, and $$NS$$ is the set of non-splittable flows. $$u_{ij}$$ is the capacity of edge $$(i, j)$$.

I am a novice in linear programming. On paper, using two simple graphs, this formulation seems to work fine.

I would appreciate it if someone could point out if there is any problem with this formulation.

• I don't quite know what exactly you are looking for. It's a legitimate linear programming problem alright and as long as the costs $c_{ij}^f$ are positive, it's also guaranteed to have a solution because your solution variables are required to be positive. Are you asking whether the model is reasonable? We can't tell you anything about that because we don't know in detail what you are trying to model. – Wolfgang Bangerth Oct 5 '18 at 3:00
• Thank you @WolfgangBangerth. I wasn't sure if my problem formulation is a legitimate LP. Also, to force the non-splittable flows to follow one path only, without turning this problem into a MIP, I added this constraint: $$x_{ij}^f \ge \begin{cases} 0 & , & f \in S\\ d_f & , & f \in NS\\ \end{cases} \quad \forall (i, j) \in E$$ So, I wanted to know whether this constraint does what I expect it to do or not. – Corey Oct 5 '18 at 7:31
• We don't know -- we don't know what all of your variables are supposed to mean. Your problem sounds like it is bounded from below, but I can't say whether your constraints allow for at least one feasible point. – Wolfgang Bangerth Oct 5 '18 at 21:25
• On another forum, someone commented: "your program does not allow $x^f_{ij}$ to be 0 if $f \in NS$, which seems incorrect. You have to use binary variables for $f \in NS$ and $(i,j) \in E$ to ensure that $x^f_{ij}$ is either $0$ or $d_f$ ". It is not clear to me why the program should allow $x^f_{ij}$ to be 0 if $f \in NS$. Sadly he didn't elaborate on this point. Can someone please tell me what he meant by this? – Corey Oct 6 '18 at 9:38

With your current model you are forcing your non splittable flows to be equal to your demand on all arcs ( $$x^f_{ij} \geq d_f, \forall f \in NS$$). Unless there is a single path from your source to your target this is going to make your problem infeasible, as the flow conservation constraints are going to conflict with this. I am afraid that for non splittable flows you do not have many alternatives to model whether or not a flow goes through an arc using a binary variable, effectively turning your problem into a MIP.
Edit 1: To model the problem as a MIP, for the non-splittable flows you need to replace the $$x_{ij}^f$$ linear variables by $$y_{ij}^f$$ binary variables representing if the complete flow goes through arc $$ij$$ or not. You should then rewrite your constraint and objective function by replacing for non splittable flows $$x_{ij}^f$$ by $$y_{ij}^fd_f$$