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

Let’s start with some helper code:

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

Minimum spanning tree

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

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

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.