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 at 6:18

Your Answer

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

Browse other questions tagged or ask your own question.