5 ms·

Traveling Salesman Problem Visualization [video]

89 points by CarolineW 10y ago

mmanfrin 10y ago
Why is this linked to someone's G+ page? https://www.youtube.com/watch?v=SC5CX8drAtU https://www.youtube.com/watch?v=SC5CX8drAtU
- dang 10y ago
  I assumed it was someone involved with the project, but since there's no obvious sign of that, we've changed the url from https://plus.google.com/+TimHarfordEcon/posts/bWijuaPkzfR https://plus.google.com/+TimHarfordEcon/posts/bWijuaPkzfR.
  - DanBC 10y ago
    Tim Harford is a UK economist who also presents "More or Less" on BBC Radio Four. He draws attention to a lot of other stuff on his social media profiles. http://www.bbc.co.uk/programmes/b006qshd http://www.bbc.co.uk/programmes/b006qshd So although it's not the original source (and the original source is better) he's not just some Internet random.
dandermotj 10y ago
This is awesome
jypepin 10y ago
This is really nice. I find this kind of visualization making understanding algorithms way easier.
wolfgke 10y ago
A much better method than those that are shown in the video is to optimize over the subtour elimination polytope by using a cutting plane algorithm. The necessary separation problem for the set of the subtour elimination inequalities can be solved by computing a minimum cut. This gives a usually very good lower bound for the value of the minimum tour. Unluckily the optimum solution over the subtour elimination polytope can be fractional. This problem can for example be solved by branch & bound (or even better branch & cut) algorithms or by randomized rounding (a more heuristic method for which in general one can nevertheless often prove strict mathematical results). Full Disclosure: I currently write a PhD thesis in mathematics on some geometric questions in the theory of cutting planes.
- eanzenberg 10y ago
  Could you either 1) simplify the explanation using simpler english or 2) provide a paper or thesis which illustrates your point?
  - revelation 10y ago
    Remember linear programs? E.g. min 10x + 5y s.t. x <= 10 y >= 5 x+y = 8 (Not very useful example) Now we can extend normal linear programs to what is known as Mixed-integer linear programming (MILP). This allows us to specify the domain of variables, i.e. we can say variable x must be a positive integer or variable y must be binary. (This extension instantly makes solving generic MILPs NP-hard because obviously we can transform any e.g. 3-SAT problem into an equivalent MILP problem) MILPs can also be used to solve the Traveling Salesman (TSP) problem. You use a binary variable for every possible pair of cities or edge the salesman could travel on that specifies if the edge is used or not. Since you want a loop, you also add a constraint for each city that it is entered and exited exactly once using the edge variables. At this point, you could think we are done: we enter and exit each city once, so we have a loop and since we minimise the sum of edge costs, we also have the optimal loop. Unfortunately, our formulation is incomplete because it allows a loophole for the solver: doing multiple tours or subtours. If we have a TSP with 5 cities, the solver could choose the edges such that you have two loops or subtours, e.g. one with 3 and another with 2 cities. That would be perfectly consistent with our formulation since each city is still entered and exited exactly once. It's not a valid solution for the TSP however since we require one single loop, not two unconnected ones. To fix this problem, we need to add what are known as "subtour elimination constraints". These check that for every partition of our city set into two sets A and B, the cities in A and B are connected, i.e. we have one edge leaving A for B and another returning from B to A (or vice versa). Unfortunately, since we need to do this for every possible combination of sets A and B, we would have to add exponentially many of these subtour elimination constraints, and of course for very large TSPs even enumerating all sets A and B is already infeasible. So what is done in practice is to first leave out all subtour elimination constraints, since this is what causes the exponential explosion (so far, our problem was polynomial in size). You then solve the linear relaxation of the MILP, i.e. you pretend that the binary constraints on the edge variables do not exist and use Simplex to solve the resulting linear problem. Then you create a weighted graph: the cities become vertices, and the edge weights are given by the (fractional) values of the edge variables. For this graph, compute the minimal cut using your favourite polynomial time algorithm. This gives you three things: a partition of the cities into two sets A and B, and a value for the flow between these two sets. If the flow is less than 2, you have found a violation of the subtour elimination constraint for sets A and B. You add that one constraint to the solver (cutting the invalid solution) and start anew. This process can be fully integrated into a branch & bound or branch & cut solver for MILPs. (I'm sure wolfgke can give a much better explanation, though)
karussell 10y ago
If you are looking for a simple, powerful but fast open source library that solves not only simple but real world TSPs (with time windows etc) and the more complex vehicle routing problems then have a look into jsprit: https://github.com/graphhopper/jsprit https://github.com/graphhopper/jsprit (note: I'm one of the GraphHopper founders)

89 points by CarolineW 10y ago

Why is this linked to someone's G+ page? https://www.youtube.com/watch?v=SC5CX8drAtU https://www.youtube.com/watch?v=SC5CX8drAtU

dang 10y ago
I assumed it was someone involved with the project, but since there's no obvious sign of that, we've changed the url from https://plus.google.com/+TimHarfordEcon/posts/bWijuaPkzfR https://plus.google.com/+TimHarfordEcon/posts/bWijuaPkzfR.
- DanBC 10y ago
  Tim Harford is a UK economist who also presents "More or Less" on BBC Radio Four. He draws attention to a lot of other stuff on his social media profiles. http://www.bbc.co.uk/programmes/b006qshd http://www.bbc.co.uk/programmes/b006qshd So although it's not the original source (and the original source is better) he's not just some Internet random.

dandermotj 10y ago

This is awesome

jypepin 10y ago

This is really nice. I find this kind of visualization making understanding algorithms way easier.

wolfgke 10y ago

A much better method than those that are shown in the video is to optimize over the subtour elimination polytope by using a cutting plane algorithm. The necessary separation problem for the set of the subtour elimination inequalities can be solved by computing a minimum cut. This gives a usually very good lower bound for the value of the minimum tour. Unluckily the optimum solution over the subtour elimination polytope can be fractional. This problem can for example be solved by branch & bound (or even better branch & cut) algorithms or by randomized rounding (a more heuristic method for which in general one can nevertheless often prove strict mathematical results). Full Disclosure: I currently write a PhD thesis in mathematics on some geometric questions in the theory of cutting planes.

eanzenberg 10y ago
Could you either 1) simplify the explanation using simpler english or 2) provide a paper or thesis which illustrates your point?
- revelation 10y ago
  Remember linear programs? E.g. min 10x + 5y s.t. x <= 10 y >= 5 x+y = 8 (Not very useful example) Now we can extend normal linear programs to what is known as Mixed-integer linear programming (MILP). This allows us to specify the domain of variables, i.e. we can say variable x must be a positive integer or variable y must be binary. (This extension instantly makes solving generic MILPs NP-hard because obviously we can transform any e.g. 3-SAT problem into an equivalent MILP problem) MILPs can also be used to solve the Traveling Salesman (TSP) problem. You use a binary variable for every possible pair of cities or edge the salesman could travel on that specifies if the edge is used or not. Since you want a loop, you also add a constraint for each city that it is entered and exited exactly once using the edge variables. At this point, you could think we are done: we enter and exit each city once, so we have a loop and since we minimise the sum of edge costs, we also have the optimal loop. Unfortunately, our formulation is incomplete because it allows a loophole for the solver: doing multiple tours or subtours. If we have a TSP with 5 cities, the solver could choose the edges such that you have two loops or subtours, e.g. one with 3 and another with 2 cities. That would be perfectly consistent with our formulation since each city is still entered and exited exactly once. It's not a valid solution for the TSP however since we require one single loop, not two unconnected ones. To fix this problem, we need to add what are known as "subtour elimination constraints". These check that for every partition of our city set into two sets A and B, the cities in A and B are connected, i.e. we have one edge leaving A for B and another returning from B to A (or vice versa). Unfortunately, since we need to do this for every possible combination of sets A and B, we would have to add exponentially many of these subtour elimination constraints, and of course for very large TSPs even enumerating all sets A and B is already infeasible. So what is done in practice is to first leave out all subtour elimination constraints, since this is what causes the exponential explosion (so far, our problem was polynomial in size). You then solve the linear relaxation of the MILP, i.e. you pretend that the binary constraints on the edge variables do not exist and use Simplex to solve the resulting linear problem. Then you create a weighted graph: the cities become vertices, and the edge weights are given by the (fractional) values of the edge variables. For this graph, compute the minimal cut using your favourite polynomial time algorithm. This gives you three things: a partition of the cities into two sets A and B, and a value for the flow between these two sets. If the flow is less than 2, you have found a violation of the subtour elimination constraint for sets A and B. You add that one constraint to the solver (cutting the invalid solution) and start anew. This process can be fully integrated into a branch & bound or branch & cut solver for MILPs. (I'm sure wolfgke can give a much better explanation, though)

karussell 10y ago

If you are looking for a simple, powerful but fast open source library that solves not only simple but real world TSPs (with time windows etc) and the more complex vehicle routing problems then have a look into jsprit: https://github.com/graphhopper/jsprit https://github.com/graphhopper/jsprit (note: I'm one of the GraphHopper founders)