This is the fiftieth 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 solve three graph problems: vinimum spanning tree, vertex cover and edge cover.

Table of Contents

Helpers

Let’s start with some helper code:

using MilpManager.Abstraction;
using MilpManager.Implementation;
using OrToolsMilpManager.Implementation;
using System;
using System.Collections.Generic;
using System.Linq;

namespace MST
{
    class Program
    {
        static void Main(string[] args)
        {
            Vertex a = new Vertex();
            Vertex b = new Vertex();
            Vertex c = new Vertex();
            Vertex d = new Vertex();

            Edge ab = new Edge { Weight = 1, A = a, B = b };
            Edge bc = new Edge { Weight = 2, A = b, B = c };
            Edge ac = new Edge { Weight = 1, A = a, B = c };
            Edge ad = new Edge { Weight = 3, A = a, B = d };

            a.Edges.Add(ab);
            b.Edges.Add(ab);

            a.Edges.Add(ac);
            c.Edges.Add(ac);

            a.Edges.Add(ad);
            d.Edges.Add(ad);

            b.Edges.Add(bc);
            c.Edges.Add(bc);

            var solver = new OrToolsMilpSolver(5);

            var edges = new[] { ab, bc, ac, ad };
            
            foreach(var edge in edges)
            {
                edge.Var = solver.CreateAnonymous(Domain.BinaryInteger);
            }

            var vertices = new[] { a, b, c, d };

            foreach (var vertex in vertices)
            {
                vertex.Var = solver.CreateAnonymous(Domain.BinaryInteger);
            }

            var cost = Constraints(solver, edges, vertices);

            solver.MakeGoal(GoalType.Minimize, cost);
            solver.Solve();

            Console.WriteLine("Vertices");
            foreach (var vertex in vertices)
            {
                Console.WriteLine(solver.GetValue(vertex.Var));
            }

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

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

    class Vertex
    {
        public List< Edge> Edges { get; set; }
        public IVariable Var { get; set; }

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

    class Edge
    {
        public IVariable Var { get; set; }
        public Vertex A { get; set; }
        public Vertex B { get; set; }
        public int Weight { get; set; }

    }

}

using MilpManager.Abstraction;

using MilpManager.Implementation;

using OrToolsMilpManager.Implementation;

using System;

using System.Collections.Generic;

using System.Linq;

namespace MST

{

class Program

{

static void Main(string[] args)

{

Vertex a = new Vertex();

Vertex b = new Vertex();

Vertex c = new Vertex();

Vertex d = new Vertex();

Edge ab = new Edge { Weight = 1, A = a, B = b };

Edge bc = new Edge { Weight = 2, A = b, B = c };

Edge ac = new Edge { Weight = 1, A = a, B = c };

Edge ad = new Edge { Weight = 3, A = a, B = d };

a.Edges.Add(ab);

b.Edges.Add(ab);

a.Edges.Add(ac);

c.Edges.Add(ac);

a.Edges.Add(ad);

d.Edges.Add(ad);

b.Edges.Add(bc);

c.Edges.Add(bc);

var solver = new OrToolsMilpSolver(5);

var edges = new[] { ab, bc, ac, ad };

foreach(var edge in edges)

{

edge.Var = solver.CreateAnonymous(Domain.BinaryInteger);

}

var vertices = new[] { a, b, c, d };

foreach (var vertex in vertices)

{

vertex.Var = solver.CreateAnonymous(Domain.BinaryInteger);

}

var cost = Constraints(solver, edges, vertices);

solver.MakeGoal(GoalType.Minimize, cost);

solver.Solve();

Console.WriteLine("Vertices");

foreach (var vertex in vertices)

{

Console.WriteLine(solver.GetValue(vertex.Var));

}

Console.WriteLine("Edges");

foreach(var edge in edges)

{

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

}

Console.WriteLine("Cost");

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

}

class Vertex

{

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

public IVariable Var { get; set; }

public Vertex()

{

Edges = new List< Edge>();

}

class Edge

{

public IVariable Var { get; set; }

public Vertex A { get; set; }

public Vertex B { get; set; }

public int Weight { get; set; }

}

Data structures for graph and code for bookkeeping. The real part is in Constraints methods.

Minimum spanning tree

static IVariable Constraints(IMilpSolver solver, Edge[] edges, Vertex[] vertices) { foreach (var vertex in vertices) { var sum = solver.Operation(OperationType.Addition, vertex.Edges.Select(e => e.Var).ToArray()); sum.Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1)); } solver.Operation(OperationType.Addition, edges.Select(e => e.Var).ToArray()).Set(ConstraintType.Equal, solver.FromConstant(vertices.Length - 1)); var cost = solver.Operation(OperationType.Addition, edges.Select(e => e.Var.Operation(OperationType.Multiplication, solver.FromConstant(e.Weight))).ToArray()); return cost; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static IVariable Constraints(IMilpSolver solver, Edge[] edges, Vertex[] vertices)
{
foreach (var vertex in vertices)
{
var sum = solver.Operation(OperationType.Addition, vertex.Edges.Select(e => e.Var).ToArray());
sum.Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1));
}

solver.Operation(OperationType.Addition, edges.Select(e => e.Var).ToArray()).Set(ConstraintType.Equal, solver.FromConstant(vertices.Length - 1));

var cost = solver.Operation(OperationType.Addition, edges.Select(e => e.Var.Operation(OperationType.Multiplication, solver.FromConstant(e.Weight))).ToArray());

return cost;
}

For every vertex we calculate the disjunction of the variables representing the edges coinciding with the vertex. Calculated value must be at least one meaning that there is at least one edge chosen for the solution.

Next, we make sure that we have exactly $|V| - 1$ edges in the solution.

Finally, the cost is the sum of the weights.

We also need constraints for the MST being a connected graph, otherwise we may end up with forest and not a tree.

Vertex cover

static IVariable Constraints(IMilpSolver solver, Edge[] edges, Vertex[] vertices)
{
	foreach (var edge in edges)
	{
		edge.A.Var.Operation(OperationType.Addition, edge.B.Var).Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1));
	}

	var cost = solver.Operation(OperationType.Addition, vertices.Select(v => v.Var).ToArray());

	return cost;
}

static IVariable Constraints(IMilpSolver solver, Edge[] edges, Vertex[] vertices)

{

foreach (var edge in edges)

{

edge.A.Var.Operation(OperationType.Addition, edge.B.Var).Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1));

}

var cost = solver.Operation(OperationType.Addition, vertices.Select(v => v.Var).ToArray());

return cost;

}

For every edge we make sure that at least one of its endings is included in the solution. The cost is the number of selected vertices.

Edge cover

static IVariable Constraints(IMilpSolver solver, Edge[] edges, Vertex[] vertices)
{
	foreach (var vertex in vertices)
	{
		var sum = solver.Operation(OperationType.Addition, vertex.Edges.Select(e => e.Var).ToArray());
		sum.Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1));
	}

	var cost = solver.Operation(OperationType.Addition, edges.Select(e => e.Var).ToArray());

	return cost;
}

static IVariable Constraints(IMilpSolver solver, Edge[] edges, Vertex[] vertices)

{

foreach (var vertex in vertices)

{

var sum = solver.Operation(OperationType.Addition, vertex.Edges.Select(e => e.Var).ToArray());

sum.Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1));

}

var cost = solver.Operation(OperationType.Addition, edges.Select(e => e.Var).ToArray());

return cost;

}

For every vertex we make sure that there is at least one selected edge. The cost is the number of the edges.

Analysis

All three methods look very easy but as for now we know polynomial time solutions for only two of them — the MST and the edge cover. The vertex cover is too hard. What’s more, OrTools or CPLEX solver don’t find optimal solutions for those problems using default settings.