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

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....

• this "all-or-nothing" constraint makes the problem hard, so there is no hope (in the complexity theory sense) that there is a reasonable LP formulation for this. – Marco Lübbecke Dec 4 '19 at 18:06

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
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}