# Min-cost flow with per-edge flow conservation

I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint.

Instead of the summed outgoing flow equaling the summed incoming flow for each node:
$$\sum_i f_{i,n} = \sum_j f_{n, j} \ \forall n$$ The flow of each outgoing edge should equal the summed incoming flow for each node:
$$\sum_i f_{i,n} = f_{n, m} \ \forall n, m$$

In other words: The incoming flow is replicated along all outgoing edges.

I wonder if:
1.) This problem has a particular name in the literature
2.) It has an optimal integral solution when all edge capacities are integral

• Are you sure about the definition of per-edge flow conservation? This would result in increasing the total flow while traversing the network from the origin to the destination. Suppose the incoming flow to a node is 100 and there are five outgoing edges from that node. Based on your constraint, the total outgoing flow would be 500. Commented Aug 6, 2020 at 6:18

## 1 Answer

There is a well-studied problem close to your one: Integral Flow With Multipliers. It was proved to be NP-hard in the seminal Sartaj Sahni's paper in computational complexity theory (see section 2.2 of the paper). Another interesting, more recent paper can be found here.