4 ms·

it depends on your problem, on what do you need, ... there are heuristics for trying to finde the best results, some are optimized for speed... i have never see

it depends on your problem, on what do you need, ... there are heuristics for trying to finde the best results, some are optimized for speed... i have never seen a better heuristic than the k-opt-heuristic (implemented in LKH), not for speed, not for the results. there are some genetic algorithms, but they are much slower, but can find sometimes results who are a little better. (see the 100000 node mona-lisa tsp problem. lkh founds a tour with the length of 5757199, a genetic algorithm founds a tour with the length of 5757191, the best exact solver concorde founds the lower bound of 5757084 (so there is a gap of 107) after calculating a time of "11.5 CPU years"). heuristics have always the problem, that you can't not say if the found result is the optimum or not. so if you have to find the optimum, you have to take an exact solver (for bigger problems. for problems with <10000 nodes there are heuristics who find the optimum to 99%) 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.

wolfgke 10y ago
> 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.

wolfgke 10y ago

> 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.