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:

```class Vertex
{
public List Edges { get; set; }
public string Name { get; set; }

public Vertex()
{
Edges = new List();
}
}

class Edge
{
public IVariable Flow { get; set; }
public Vertex A { get; set; }
public Vertex B { get; set; }
public int Capacity { get; set; }
}
```

Let’s now initialize the graph:

```Vertex v0 = new Vertex { Name = "0" };
Vertex v1 = new Vertex { Name = "1" };
Vertex v2 = new Vertex { Name = "2" };
Vertex v3 = new Vertex { Name = "3" };
Vertex v4 = new Vertex { Name = "4" };
Vertex v5 = new Vertex { Name = "5" };
Vertex v6 = new Vertex { Name = "6" };
Vertex v7 = new Vertex { Name = "7" };

Edge e01 = new Edge { Capacity = 3, A = v0, B = v1 };
Edge e02 = new Edge { Capacity = 2, A = v0, B = v2 };
Edge e03 = new Edge { Capacity = 2, A = v0, B = v3 };
Edge e14 = new Edge { Capacity = 5, A = v1, B = v4 };
Edge e15 = new Edge { Capacity = 1, A = v1, B = v5 };
Edge e24 = new Edge { Capacity = 1, A = v2, B = v4 };
Edge e25 = new Edge { Capacity = 3, A = v2, B = v5 };
Edge e26 = new Edge { Capacity = 1, A = v2, B = v6 };
Edge e35 = new Edge { Capacity = 1, A = v3, B = v5 };
Edge e47 = new Edge { Capacity = 4, A = v4, B = v7 };
Edge e57 = new Edge { Capacity = 2, A = v5, B = v7 };
Edge e67 = new Edge { Capacity = 4, A = v6, B = v7 };

var solver = new CplexMilpSolver(10);

var edges = new[] { e01, e02, e03, e14, e15, e24, e25, e26, e35, e47, e57, e67 };

foreach (var edge in edges)
{
edge.Flow = solver.CreateAnonymous(Domain.PositiveOrZeroInteger);
}

var vertices = new[] { v0, v1, v2, v3, v4, v5, v6, v7 };
```

Now we need to add two constraints.

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

```// Flow of a link cannot exceed capacity of that link
foreach (var edge in edges)
{
edge.Flow.Set(ConstraintType.LessOrEqual, solver.FromConstant(edge.Capacity));
}
```

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

```// Incoming node flow is equal to outgoing flow node
foreach (var vertex in vertices.Except(new []{v0, v7}))
{
solver.Operation(OperationType.Addition, edges.Where(e => e.B == vertex).Select(e => e.Flow).ToArray())
.Set(ConstraintType.Equal, solver.Operation(OperationType.Addition, edges.Where(e => e.A == vertex).Select(e => e.Flow).ToArray()));
}
```

Now we need to solve the program:

```IVariable cost = solver.Operation(OperationType.Addition, e01.Flow, e02.Flow, e03.Flow).MakeGoal(GoalType.Maximize);