&gt; heuristics have always the problem, that you can&#x27;t not say if the found result is the optimum or not.<p>Even worse: Heuristics have the problem that you usually can&#x27;t give any metric on <i>how good you even are</i>. If you use an ILP (Integer Linear Programming) based approach if you found an integral solution the optimal solution of the LP relaxation gives you a lower bound (if you minimize) on the optimal length of the tour - so you can tell exactly that you only can get, say, 1% better and cancel any further computation, since you consider this as good enough.<p>&gt; to get an idea if you are close to an optimum or not, there is the lower bound call &quot;held-karp-lower-bound&quot;. you have to calculate a mst, a one-tree and some extra stuff to get it. than you can calculate the difference between both values.<p>The Held-Karp bound is the same as the optimal value over the subtour elimnination polytope (Theorem 21.34 in Korte, Vygen: Combinatorial Optimization - Theory and Algorithms (5th edition)). This is rather where one <i>starts</i> when one uses an ILP based approach.