Max flow problem without splitting the flow from the supply nodes - LP formulation help

Question

Since max flow formulation can be easily solved using LP, I wanted to ask the following:

I am trying to solve a simple max flow problem where the graph is bipartite but with one added constraint. The constraint is that the flow from any supply node '$a$' should not be split, i.e. suppose I have a supply at node '$a$' of 4 units and have arcs $(a,x)$, $(a,y)$, and $(a,z)$, then the entire 4 units of supply should go through one and only one arc.

Is there an LP formulation for this? I can model it using integer variables....

Answer 1

If you define binary variables for each of the arcs let's say $$m_{ij} \ \ \forall i\in \text{supply}\ \ \text{and} \ \ j \in \text{demand}$$ then you can add the following constraint to the model: $$\sum_j m_{ij} = 1$$ and the shipment then can be limited as the following ($M$ is a large number to relax $s_{ij}$ if necessary): $$s_{ij} \le M \cdot m_{ij}$$ In this formulation $s_{ij}$ is still continuous variable

Answer 2

Add binary variables $y_{ai}$ and the following constraints: \begin{align} y_{ax}+ y_{ay} + y_{za} &\le 1\\ x_{ai} &\le 4 y_{ai} \end{align}