Second Solution, First Failure

Wow, it’s been awhile since I posted, which was on January 26th. That’s because I don’t like failure and failure was where I wound up.

But let’s back up a bit. I was referred to Developing Customized Branch-&-Cut algorithms on the python-mip site. So I went back there and grabbed their sample code showing a Branch and Cut solution.

When reading over the program I noticed that it was not using a triangular matrix, but a rectangular one. This is because the distance from A to B might not be the same as the distance from B to A! You can have one way streets or bridges, or whatever. And more importantly, computer science types like to thing of arbitrary nodes.

I needed to modify my triangle.py code to give me a bi-directonal matrix. I won’t got into the code, which you can see here, on GitHub, except to note that I explicitly do a few odd things.

The first is that I set the date and time to the middle of the night in the middle of the week. You see, google maps really wants to give you shortest times, not shortest distances. And times depends heavily on current traffic, or if you are looking in the future, at expected traffic. I really wanted shortest distance, well, because that’s what the TSP is all about. Ok, it is about cost, not distance, which could be construed as time but for my purposes, I’m concerned with distance. I also look at the distance between A and B and between B and A and choose the shorter one. It is pretty easy to find routes in google maps that just don’t make sense. I’m pretty sure they’re doing things like sticking to main roads, not backroads, but this is the best API I have available. I looked at Apple Maps and Open Street Maps and I kept on seeing time, not distance. I’d love to be proven wrong here.

I ran than program, which writes out some python, and then pasted that into subtour.py, which you can see on GitHub also, but it is just the sample code from the python-mip side, modified in a few ways.

You see, I found that when I ran the program it would only give me the optimal length, not the route. And I needed the know the route. I eventually found out that that solution could be written out as a file, but it consisted of strange names, like var123, not Ashuelot Bridge. So I spent a lot of time trying to get it to spit out the route, working with the helpful people at the python-mip email list. And that’s what you see uploaded.

The good news is that it runs fast, it takes under 15 seconds to run the 53 node problem. The bad news is, well, I don’t trust the answer. I never code get it to graph the correct solution. The program I uploaded to GitHub was incorrect. I was able to run this on a small subset of data, and it was provably wrong.

I spent more than a month, part-time obviously, trying to get this to work and eventually I gave up. I guess I should show my work, proving to myself that this approach was flawed, but why? I’m tired of failure here.