> heuristics have always the problem, that you can't not say if the found result is the optimum or not. Even worse: Heuristics have the problem that you usuall

> heuristics have always the problem, that you can't not say if the found result is the optimum or not. Even worse: Heuristics have the problem that you usually can't give any metric on how good you even are. 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. > to get an idea if you are close to an optimum or not, there is the lower bound call "held-karp-lower-bound". 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. 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 starts when one uses an ILP based approach.