Efficiency of Local Search

Local search heuristics are an important class of algorithms for obtaining good solutions for hard combinatorial optimization problems. Important issues for these heuristics are solution quality and computational time. A local search heuristic starts with an initial solution, and iteratively advances to a neighboring solution of the current solution. This is repeated until some stopping criterion is met. The neighborhood is a critical issue in a local search heuristic. It directly influences the local behavior of a local search heuristic, since it restricts the choice of a new solution in a single iteration. This determines the local efficiency of a local search heuristic. On the other side, this local behavior also influences the global behavior, i.e. the sequence of feasible solutions obtained by the local search heuristic. This sequence of solutions represents the navigational behavior of the local search heuristic and determines the global efficiency of a local search heuristic. In the first part of the thesis, we consider neighborhoods of large size that can be explored in a fast manner, in order to reach local optima of good quality in less time. We consider a single machine and a parallel machine scheduling problem. We develop very large-scale neighborhoods for these two scheduling problems. For all the introduced neighborhoods, we explain what solutions they contain and how the neighborhood is efficiently explored to obtain a better neighbor. We also compare their performance to basic neighborhoods regarding solution quality and running time by conducting computational tests. In the second part of the thesis, we examine the global efficiency in terms of solution quality obtained at the end of a local search heuristic. We obtain performance guarantees for local optima of certain neighborhoods for two parallel machine scheduling problems. Although the found performance guarantees are worse compared to constructive heuristics (however, for our cases the differences are quite small), the advantage of giving performance guarantees for local optima is that these guarantees hold for all solutions which are locally optimal and not only for a single solution as for most constructive heuristics.