Max Flow Edge Constraints

1
votes

How would one solve a max flow problem in which some edges in the graph must have a flow = 3n where n is a non-negative integer? In other words, how do you impose constraints that certain edges must have a flow divisible by 3? For example, these edges may have flow 0, 3, 6, 9... but may not have flow 1, 2, 4, 5... Ideally I would like a way to compute the max flow on a graph like this and also the flow on each edge in the max flow configuration.

1
algorithmlinear-programmingmax-flow
en.wikipedia.org/wiki/Integer_programming if nobody has any better ideas – mcdowella
@mcdowella Pretty sure the divisibility constraint makes this NP-hard, so that's what I would try too. – David Eisenstat

1 Answers

1
votes

Basically, implement an algorithm for finding max flow, and build in your constraint.

What I mean is, have a look at the Ford-Fulkerson algorithm.
Notice that in line 2.1 of the algorithm (as described in Wikipedia) you find some

enter image description here

Now, this value is based on the minimum of each edge on the path. This is where you check if one of these edges has some constraint, and then change the value of c_f(p) accordingly.