Integer Programming for Graph Theory and Others with Python: 03 — Minimum Spanning Tree and Travelling Salesman

The Great Deku Tree from The Legend of Zelda, painted by Lockwork

Hello everyone! I am so glad you reached Episode 3 of my series! Today we will address 2 generic problems in Graph Theory, and see how to solve them with Integer Programming!

Minimum Spanning Tree

The Graph used for this Minimum Spanning Tree problem

The objective here is to connect all the nodes directly or indirectly with the lowest cost possible, without creating cycles. In other words, minimize the sum of the used edges’ cost. Since we already reached this conclusion, here is the code for the Variable declarations and the Objective Function:

Looking at an Undirected Graph with 5 nodes, we can easily see that we only need 4 edges to connect them all, right? If we have 2 nodes, we only need 1 edge to connect them. If we add another node, we need to add another edge to one of the connected nodes and the new node. So, the rule is:

For a graph with N nodes, you need N-1 edges to build its Minimum Spanning Tree

Here is the code for the constraint:

And now, we just need to make sure that each node has at least one edge connected to it:

So, the number of edges is set, and all the nodes must have at least 1 edge connected to them. That’s all it takes to give us the optimal solution, right?

!!! WRONG !!!

The model above might work in some scenarios, but not all of them. Why? Because it does not guarantee the absence of cycles.

How to prevent cycles?

Ok, this is going to sound a bit expensive, but it’s actually the way to do this: if there is a cycle, it means that there is a subgraph of N nodes that has N edges. Therefore, we need to guarantee that, for any subgraph of N nodes, the sum of edges is smaller or equal to N-1. This is going to be a lot of code, but it’s just repetitive:

And here we are, with the full model coded. If we run it, we finally get our Minimum Spanning Tree:

Final solution for the Minimum Spanning Tree Problem

Scalability issues

There were 13 subgraphs that were not used because the original Graph doesn’t have that many edges, but if we were dealing with a Complete Graph (all nodes are directly connected to each other) there would be 13 extra constraints. And if it was a Complete Graph with 6 edges there would be 41 constraints…

… and if the Graph had 7 edges it would have 98 constraints…

As you can see, it grows exponentially, so it can become a pretty tough problem to solve when Graphs are big and dense. Anyway, here is the model :D

The Travelling Salesman

Salesman Comic Strip, by DansCartoons

This is another famous, arguably more famous, and hard-to-scale problem! It consists of finding the Shortest Path from a Point to itself while visiting every point only once, just like a Salesman visiting every destination to sell his products and returning to his house in the end.

Graph used for this example of the Travelling Salesman Problem

Since we’re looking for the Shortest Path, this is a minimization problem, where we are minimizing the sum of the used edges multiplied by their respective weights.

The constraints are the following:

1 — the number of edges must be equal to the number of nodes;

This one is pretty obvious: think about drawing polygon: if it has 4 corners, you need 4 lines, if it has 5 corners you need 5 lines… and drawing a polygon is like drawing a Travelling Salesman Path on a graph with the same number of nodes/corners.

2 — there cannot be cycles in any subgraph;

Similarly to the Minimum Spanning Tree Problem’s model, all subgraphs of N nodes must have a number of edges smaller than N.

If we run the solver, we get the solution Start — C — B — D — Start , with a cost of 9. And that’s how we save our Salesman’s legs from all the walking!

Solution for the Travelling Salesman Problem

Everyday is Leg Day for the Travelling Salesman

Next Episode: Array Sorting with Integer Programming and No Objective Function

See you next time! :D