Fitness Landscape Analysis and Algorithm Selection for Assignment Problems

The field of optimization has a wide range of applications in the real world. The operation of trucks, ships, cranes, production lines, hospitals, or warehouses results in many decision situations that affect efficiencies, business capabilities, and costs. Deterministic and stochastic models formalize the decision situations as well as their objectives. Exact and heuristic techniques are employed to solve these models efficiently. The resulting solutions are then used to derive the respective decisions. A large range of such solving algorithms are available, but which outperform each other in different situations. It is thus a major problem to decide which algorithm instance should be applied to solve a specific model. It is the goal of this thesis to devise and evaluate methods that are able to solve this so called algorithm selection problem. We will evaluate whether an improved solving algorithm can be found that reuses existing approaches. The goal is to evaluate such an algorithm when applied to well-known models and evaluate its performance. In this light, research and development efforts from three domains are described and studied. First, fitness landscape analysis is a method applicable to characterize models and their instances through a set of features. We will provide an overview on high-level characteristics that influence the performance of solving algorithms. In this thesis a new method termed directed walk and new features are devised, different variants thereof are analyzed, and new ideas for algorithms are given. Second, the algorithm selection problem is solved in two case studies. Several thousand runs have been performed on a wide range of different benchmark instances. Thereby, the performance of a range of algorithms is recorded. In these two studies we will evaluate a classification-based approach to the algorithm selection problem. Thereby, we will compare the performances of algorithms and relate those to the landscape characteristics. We will show that a combined approach performs better than an individual algorithm. Third, the general research model of operations research is introduced and it is discussed how such results can be transferred to other models and domains. Thereby, we discuss the steps involved to move from a real-world problem to a scientific model and further to a solution through an efficient solver. Finally, we introduce software systems that support such tasks and which have been created by the author in the course of his studies.