ILP Part 53 — Max flow – Random IT Utensils

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:

Graph

We use the following records:

class Vertex
{
	public List<Edge> Edges { get; set; }
	public string Name { get; set; }

	public Vertex()
	{
		Edges = new List<Edge>();
	}
}

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

class Vertex

{

public List<Edge> Edges { get; set; }

public string Name { get; set; }

public Vertex()

{

Edges = new List<Edge>();

}

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 };

v0.Edges.Add(e01);
v0.Edges.Add(e02);
v0.Edges.Add(e03);

v1.Edges.Add(e14);
v1.Edges.Add(e15);

v2.Edges.Add(e24);
v2.Edges.Add(e25);
v2.Edges.Add(e26);

v3.Edges.Add(e35);

v4.Edges.Add(e47);

v5.Edges.Add(e57);

v6.Edges.Add(e67);

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 };

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 };

v0.Edges.Add(e01);

v0.Edges.Add(e02);

v0.Edges.Add(e03);

v1.Edges.Add(e14);

v1.Edges.Add(e15);

v2.Edges.Add(e24);

v2.Edges.Add(e25);

v2.Edges.Add(e26);

v3.Edges.Add(e35);

v4.Edges.Add(e47);

v5.Edges.Add(e57);

v6.Edges.Add(e67);

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));
}

// 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()));
}

// 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);
solver.AddGoal("Cost", cost);
solver.Solve();

Console.WriteLine("Edges");
foreach (var edge in edges)
{
	Console.WriteLine(solver.GetValue(edge.Flow));
}

Console.WriteLine("Cost");
Console.WriteLine(solver.GetValue(cost));

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

solver.AddGoal("Cost", cost);

solver.Solve();

Console.WriteLine("Edges");

foreach (var edge in edges)

{

Console.WriteLine(solver.GetValue(edge.Flow));

}

Console.WriteLine("Cost");

Console.WriteLine(solver.GetValue(cost));

That’s it.