Towards prediction of algorithm performance in real world optimisation problems

We investigate the applicability of an existing framework for algorithm runtime prediction to the field of metaheuristics, in particular applied to the real world problem of nurse rostering. Apart from predicting the runtime, we look at other performance criteria as well. These so called empirical hardness models are based on readily computable features of the problem instances. These problem features are basic properties or characteristics that are thought to be influencing the complexity of the problem instances. We follow two approaches, one in a domain specific setting, and later in a more general setting where problems are represented using a Propositional Satisfiability (SAT) formulation. Both approaches lead to accurate prediction models in a small proof-of-concept problem distribution. The framework can be used to help understanding the complexity, build algorithm portfolios and allow for quick quality approximation when the resources for computing a solution are not available.status: publishe