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

  • 1
    $\begingroup$ 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. $\endgroup$ – Ehsan Aug 6 '20 at 6:18

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.