Local search is a well-known basic tool to construct heuristic algorithms for discrete optimization problems. It repeats the operation of replacing the current solution with a better solution in its neighborhood (if there is any), until no better solution can be found in the neighborhood (i.e., local optimality is attained). After presenting basic ideas, we discuss further generalizations, improvements and ramifications of local search, including the following.
Effect of the neighborhood sizes. Larger neighborhoods usually improve the quality of local optimal solutions, but require more computational time to search the neighborhood. The trade-off between time and quality is discussed on the basis of computational results for problem MAX-SAT. Distribution of local optimal solutions, as well as the computational techniques to speed up the neighborhood search, are discussed.
Adaptive usage of neighborhoods of various sizes. By exploiting the problem structure, it is sometimes possible to prepare multiple neighborhoods of various sizes, and to use them adaptively. This may enable us to conduct deeper neighborhood search without increasing the computation time too much. An example of this type of variable depth search is explained by using the ejection chain idea for GAP (generalized assignment problem).
Combination with metaheuristics. Local search can be embedded in metaheuristic methods, such as tabu search, genetic algorithm and simulated annealing. These methods have mechanisms to escape from local optimality, and can be very effective if implemented properly. To build general purpose solvers for a wide range of real world problems, we are developing metaheuristic algorithms for a list of multiple standard problems, including MAX-SAT, GAP, CSP (constraint satisfaction problem) and RCPSP (resourced constrained project scheduling problem). Outlines of these algorithms, as well as their computational performance, are presented.
Return to the LSDO tutorial topics page