UTFacultiesEEMCSEventsPhD Defence Jesse van Rhijn | Rigorous Analysis of Local Search Heuristics

PhD Defence Jesse van Rhijn | Rigorous Analysis of Local Search Heuristics

Rigorous Analysis of Local Search Heuristics

The PhD defence of Jesse van Rhijn will take place in the Waaier Building of the University of Twente and can be followed by a live stream.
Live Stream

Jesse van Rhijn is a PhD student in the Department of Mathematics of Operations Research. Promotors are dr. B. Manthey from the Faculty of Electrical Engineering, Mathematics and Computer Science and prof.dr. T. Vredeveld from Maastricht University.

Local search heuristics are standard methods in the optimizer's toolbox. These algorithms take as an input a candidate solution to an optimization problem and iteratively compute better solutions. They are used widely in applications and often perform very well. Heuristics typically provide close-to-optimal solutions in much less running time than exact or approximation algorithms.

Despite their practical usefulness, local search heuristics often have poor performance in the worst case. For many problems we know of instances where commonly used heuristics take prohibitively long to return a solution, or where they may return solutions that are far from optimal. This considerable gap between theory and practice is not satisfactory, as we would like to have some theoretical justification for using local search heuristics in practice.

This dissertation broadly aims to enhance our understanding of local search heuristics. We analyze several heuristics using rigorous mathematical tools. Our focus is on three computational problems: the Travelling Salesperson Problem (TSP), k-Means clustering, and Max Cut.

We consider these heuristics from the perspective of worst-case and beyond-worst-case analysis. The former framework is the classical way of viewing an algorithm's performance, where one constructs an instance that provokes the worst possible behavior of an algorithm. In beyond-worst-case analysis, one instead attempts to understand the behavior of an algorithm in practice. We use in particular smoothed analysis, where one analyzes the performance of an algorithm when its input is perturbed probabilistically.

For the TSP, we perform a smoothed analysis of the running time of the well-known 2-opt heuristic. Our analysis both simplifies and improves on previous analyses, yielding the best known smoothed running time bounds for the Euclidean TSP variant. We also analyze 2-opt from a structural perspective: first, we show that counting 2-optimal solutions in complete graphs is computationally hard, and subsequently we determine the expected number of 2-optimal tours in random TSP instances. We argue that this has implications for the running time of metaheuristics.

We also analyze two variants of 2-opt. One, called X-opt, removes crossing edges in two-dimensional tours, and is known to have polynomial running time in the worst case. We show that this variant can return tours very far from optimal, and is thus not a suitable replacement for 2-opt. This even holds for random instances, where typically algorithms perform far better than on worst-case instances.

Motivated by the running time of X-opt, we define a second variant which we call Y-opt. This variant also has polynomial worst-case running time, but has essentially the same approximation guarantees as 2-opt. In this way Y-opt combines the efficiency of X-opt with the solution quality of 2-opt.

To augment these theoretical results we perform a simple numerical test comparing the approximation performance of these three algorithms on random Euclidean instances. While 2-opt and Y-opt perform as predicted, X-opt returns solutions that are much better than our theoretical results would suggest. This implies that our theoretical tools fall short of explaining its practical performance. Since these tools are rather standard in the field, this shows the need for more advanced techniques to explain the true performance of local search heuristics.

We also rigorously analyze the Hartigan-Wong method for k-Means clustering. This heuristic performs well in practice, but even its worst-case running time was not known so far. We show that even in one-dimensional instances - where k-Means can be solved optimally in polynomial time - the Hartigan-Wong method can take exponential time to find locally optimal clusterings. We also show that in higher-dimensional instances the heuristic leads to a PLS-complete local search problem, meaning that it is among the hardest local search problems.

To augment these results we also perform the first smoothed analysis of the Hartigan-Wong method. We show that for few clusters and in low dimensions, the Hartigan-Wong method has polynomial smoothed running time. While this is encouraging, our worst-case constructions do not fall under these assumptions (having either many clusters or dimensions). We therefore view this result as a stepping stone, serving to motivate research into the Hartigan-Wong method.

Lastly, we analyze the Flip heuristic for Max Cut. This heuristic shares many similarities with the Hartigan-Wong method, and as such we are able to use similar methods for both. In particular, we show that this simple heuristic yields a PLS-complete local search problem even in Euclidean instances.