Error Space Search for Combinatorial Optimization

Combinatorial optimization problems are important both theoretically and for solving real-world problems. Many resolutions to combinatorial optimization problems have been proposed in the literature. An approach attracting recent attention from researchers is combining global search with greedy algorithms, resulting in hybrid algorithms. These hybrid algorithms take advantage of the global optimization capabilities of global search algorithms while using the greedy algorithm's strength to repair invalid solutions and to explore local regions that promise good solutions. Proposals using this approach often conduct their search in solution space -- the space of possible solutions to the problem. However, surveying and evaluating recent studies using the above approach has shown that designing new algorithms that obtain impressive results when solving more challenging combinatorial optimization problems has become more and more difficult. Building on a recognition of the strengths of greedy local search, this thesis presents a new approach to the global search in hybrid algorithms, changing the search from solution space to error space. The error space is the set of errors that the greedy algorithm can make. The global search algorithm finds and passes potential error sets to the greedy algorithm, helping it avoid the mistakes it would otherwise make, and generate better solutions than it could by itself. This new approach is presented as an optimization framework. The framework is used to design two hybrid optimization algorithms to solve two different combinatorial optimization problems: the Discounted Knapsack Problem and the Set Covering Problem. Experimental results show that the resulting algorithms perform impressively, surpassing the state-of-the-art algorithms using the standard approach in many cases. This demonstrates that the proposed error space-based optimization framework is a general one that can be used effectively for a variety of combinatorial optimization problems. The thesis presents a new strategy for researchers to design algorithms for other combinatorial optimization problems and sets a new direction for research on hybrid search algorithms that can combine global search and greedy algorithms in more effective ways.