Network flow as a linear/integer programming problem with special conditional constraints

Question

Consider the classic network flow problem where the constraint is that the inflow to a vertex is equal to the sum of its outflows. Consider having a more specific constraint where the flow cannot be split between edges. The constraint is that the inflow a to a vertex v is equal to b (the amount that v has acquired from a) plus c (the outflow carried by only one of the non-visited edges of v).

The figure below demonstrates this in 3 mutually exclusive cases. The green directed edge carries an inflow of value a. Vertex b takes some value of a, then only one of the edges (disregarding the inflow edge) carries the outflow of value c=a-b (illustrated in 3 cases - the red edge represents the edge carrying the outflow, the rest of the edges should have zero outflow).

Is this constraint possible to formulate under the linear/integer programming setting ?

Thanks in advance!

Answer 1

I would think that you need a MIP formulation for that. What about the following? Assume directed arcs (this means all our flows are non-negative: $x_{i,j}\ge 0$). First write down the in-flow=out-flow balance equation:

$$ \sum_i x_{i,k} = u_k + \sum_j x_{k,j} \> \forall k$$

Here $u_k$ is what is consumed by node $k$ (could be a variable or a coefficient; not sure from the description). Then add binary variables and constraints:

$$ \begin{array}{ll} x_{k,j} \le M_{k,j} \delta_{k,j} & \forall k,j\\ \sum_j \delta_{k,j} = 1 & \forall k \\ \delta_{k,j} \in \{0,1\} \\ \end{array}$$ The coefficient $M_{k,j}$ should be chosen as small as possible (i.e. equal to the upperbound or capacity of arc $x_{k,j}$). In this case, instead of binary variables you could use SOS1 sets to model this (I usually choose the formulation with binary variables).

Of course depending on the network you may not need this (e.g. a shortest path problem will never split its flow). Note that this formulation allows multiple incoming flows, but only a single outgoing flow. Also I have ignored the source and the sink nodes, they may have additional in and outflow and need special treatment (the flow balance equation is slightly different for them).