Linear program for flow into a node should exit all on one edge

Question

Suppose I'm given a problem where I want to route some flow from a set of sources to a set of sinks in a directed graph; however, as opposed to the standard flow constraints, I also want to constrain some nodes in the following way: all flow into the node must leave along only one outgoing edge. In other words, the normal flow constraint on the non-source/non-sink nodes is the following: $$\sum_{u \in V} f_{(u, v)} - \sum_{w \in V} f_{(v, w)} = 0.$$

However, for vertex $v$, I instead want: $\sum_{u \in V} f_{u, v} - f_{(v, w)}= 0$ for exactly one outgoing edge $(v, w)$. (All other outgoing edges have zero flow.) How do I write a set of linear constraints to ensure this fact in an ILP? There must be a fairly standard way to do this but I am having trouble formulating it/finding it via searching.

Answer 1

Let $M$ be a big number.

$$\sum_{u \in V} f_{u,v} - \sum_{w \in V} f_{v,w}=0$$ We can introduce some indicator variable, $x_{v,w}= \begin{cases} 1 &, f_{v,w}>0 \\ 0 &, f_{v,w}=0 \end{cases}$

We impose the following constraints:

$$Mx_{v,w}\ge f_{v,w}$$

$$x_{v,w} \le Mf_{v,w}$$

$$\sum_{w \in V} x_{v,w}\le 1$$

Answer 2

Let $\alpha_w \geq 0$, $(v,w)\in E$, be the integer variable "the outgoing edge is w", since we just want one outgoing edge: $$ \sum_{(v,w)} \alpha_w = 1 $$

Since we want the flow to get out: $$ \sum_{(u,v)} f_{u,v} - \sum_{(v,w)} f_{v,w} = 0 $$

And since we just want one edge to work: $$ 0 \leq f_{v,w} \leq F\alpha_v $$

where $F$ is the entire flow or more.