Algorithm performance prediction for practical combinatorial optimisation problems
Promotor: dr. P. De Causmaecker , CODeS KULeuven, campus Kortrijk
This dissertation investigates algorithm performance predictions in the context of combinatorial optimisation problems. The project is inspired by existing studies on running time predictions for complete search methods solving classical decision and optimisation problems. It considers more general performance criteria in the context of incomplete methods. One of the core concepts in this thesis is the notion of empirical hardness, denoting the apparent complexity of an instance as it is observed by a particular solver. We start by proposing a general strategy allowing for the construction of prediction models for the empirical hardness of practical problem instances. This strategy is formulated at a high level, allowing it to be applied in a broad variety of settings. We apply the strategy in two case studies, each focusing on a prototypical hard combinatorial optimisation problem with practical relevance. We consider the nurse rostering problem and a generalisation of the project scheduling problem. We investigate state-of-the-art metaheuristic algorithms for both problems and demonstrate the power of the methodology in this more complicated practical context. In particular, we present practical instantiations for all ingredients of the strategy. By extensive experimentation, we succeed in realising accurate performance prediction models. We furthermore build successful applications in the form of automatic algorithm selection tools, outperforming all of their state-of-the-art components individually. Based on the experience gained through the doctoral project, we present a discussion on the application of the proposed strategy in practical settings. We focus on the important ingredients and discuss how they can be instantiated.
