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.

# Helpers

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

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.

# Vertex cover

```static IVariable Constraints(IMilpSolver solver, Edge[] edges, Vertex[] vertices)
{
foreach (var edge in edges)
{
}

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

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.