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.<p>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 &amp; bound (or even better branch &amp; cut) algorithms or by randomized rounding (a more heuristic method for which in general one can nevertheless often prove strict mathematical results).<p>Full Disclosure: I currently write a PhD thesis in mathematics on some geometric questions in the theory of cutting planes.