Efficient cluster compensation for lin-kernighan heuristics
Derek Gordon Corneil, David Michael Neto · 1999
For certain problems such as the Traveling Salesman Problem, the Lin-Kernighan heuristic and its derivatives are among the most successful algorithms known to optimization practice. It usually runs quickly, producing nearly optimal answers. Unfortunately, run times are usually longer on sharply clustered instances than on more uniform instances. This dissertation introduces efficient cluster compensation, an algorithmic technique designed to reduce the performance penalty Lin-Kernighan suffers on clustered inputs. The technique aims to decrease running times while maintaining the quality of the answers produced. The strategy is to prune unfruitful portions of the search space by incorporating extra lookahead into the guiding utility function. The lookahead takes the form of the cluster distance between two points, a value computed in constant time given modest preprocessing. Efficient cluster compensation reduces running times on nearly all inputs tested, not just sharply clustered instances. When it increases running times, the slowdown is not severe. Efficient cluster compensation therefore delivers overwhelming benefit at little or no cost. Heuristics are notorious for behaving unpredictably. Making algorithmic choices and tuning parameters is rightly described as a black art. A broader contribution of this thesis is a better understanding of the qualitative behaviour of the Lin-Kernighan heuristic. The key features of a worst-case result, Papadimitriou's proof that Lin-Kernighan solves a PLS-complete problem, are conjectured to be the cause of bad behaviour observed by Johnson. This intuition is validated by the performance improvement seen when cluster compensation is used, and by comparing several of the results with perturbed data. This thesis also introduces several novel instance generation algorithms. They are used to test the generalizability and the robustness of the experimental results reported in earlier chapters, and to test our intuition about the behaviour of the heuristic. The Lin-Kernighan heuristic is best known as a heuristic for the Traveling Salesman Problem. Yet the TSP heuristic is only one instance of the more general Lin-Kernighan strategy to which cluster compensation applies. We test cluster compensation using it in the Lin- Kernighan heuristic for the TSP and in a Lin-Kernighan heuristic for the minimum weight perfect matching problem.