Integer Programming for Graph Theory and Others with Python: 02 — Shortest Path / BigN
In the previous blog post of this series we looked at what Integer Programming is and how to use it to solve Knapsack, a combinatorial problem. This time, we are going to use IP to solve the Shortest Path Problem, famously solved on every Uber Trip or every Google Maps directions request.
What is a Graph?
Keeping it simple, a Graph is a collection of points (nodes) and lines connecting pairs of nodes (edges). Each edge can have a weight representing something like distance, and they can be directed or not. Directed graphs’ edges connect point A to point B, but that doesn’t mean that point B is connected to point A. Undirected graphs are self-explanatory.
The Shortest Path Problem
Basically, given a Graph (undirected, to keep it simple), a starting point and an ending point, we need to figure out the path that minimizes the cost. Usually the cost is the distance, but it can be other values such as time or fuel spent. In this case, we will use the fuel’s money spent (we will get to why later on, trust me).
The following image represents the graph for this problem.
Now, start with the variables. Since we want to choose which edges to use for our path, each edge will have a binary value: used or not used. Therefore, we will create an Integer Variable with a range between 0 and 1 for every edge:
Our objective function will be the sum of all our Variables multiplied with the respective cost of fuel. Of course we want to have the lowest cost of fuel, so this is a Minimization problem.
Last but not least (and this is where it gets interesting) we have the constraints!
The simplest constraints we have is that there must be an edge leaving point A and an edge entering point Z, that’s the basic part of our path. To represent this, it means that only 1 edge exiting A can be active, so either A-B or A-C or A-E is active. Since they are all binary variables, the sum of the 3 of them must be 1.
And for every other point in our graph, we follow this rule: “What goes in, must come out!”
This means that if there is an edge entering point C, there must be an edge exiting C. So, the sum of the variables that represent the edges entering C must be equal to the sum of the variables that represent the edges that exit C.
Congratulations! We have formulated the entire Shortest Path model! Now we just need to run the solver and check the solution.
The solution is: A — C — D — F — Z , with a fuel cost of 10. Pretty cool, hun? This can be applied to any Graph!
Extra constraint & BigN: dangerous apocalyptical roads!
Imagine you’re in a post-apocalyptical world, and you need a gun to protect you from those Walking Dead zombies. Some roads are dangerous, and if you plan on using those roads you must buy a gun. But guns cost money, should you buy a gun or just take the long way?
Let’s create a gun Binary Variable, that will have value 1 if you buy it. The gun will cost 5 to purchase.
The dangerous roads will be C-D , A-E and E-F. If you go through at least one of these you need to buy a gun.
Ladies and Gentleman, I present you the BigN!
Let’s sum those 3 edges. If you don’t use any of them, the sum’s result will be zero. If you do, it will be 1 or bigger. if you divide the result by an enormous number, the result will be bigger or equal to zero and smaller than 1, but never equal or bigger than 1. Of course we can divide it by 2, because it is the maximum the sum could have, but if we are using a massive graph and we cannot deduce that just from looking at it, we can play it safe and use a gigantic number.
The trick here is that the gun variable is in the optimization function, so the solver will try to minimize it, but it can only be zero if none of those 3 edges are used. Let’s run the solver and check the result!
Good news! You don’t need to face violence today to save your post-apocalyptic cash (shells, bullets, what do you think the currency would be?), because the cheapest route is A-B-D-F-Z, with a total cost of 11.
