ILP Part 53 — Max flow

This is the fifty third part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to implement Maximum flow in ILP.

We use the following graph:


We use the following records:

Let’s now initialize the graph:

Now we need to add two constraints.

First one limits the flow for a given edge — we cannot exceed the capacity link:

Second constraint says that whatever flows into the node must flow out of it. Input flow must be equal to output flow:

Now we need to solve the program:

That’s it.