PhD dissertation
Low Knowledge Algorithm Control for Constraint-Based Scheduling
Tom Carchrae
The central thesis of this dissertation is that low knowledge control methods allow non-experts to achieve high quality results from optimization technology. This is achieved through the use of algorithm control methods that automatically determine the best performing algorithms for a particular problem instance. We create and investigate mechanisms for algorithm control that do not require detailed knowledge of the problem domain or algorithm behaviour. These low knowledge control methods make decisions based only on observations of algorithm performance. The strong performance observed is not the primary result; it is that these results are possible using simple general control methods that do not require significant effort and expertise to implement.
We develop a framework for algorithm control methods and use it to present an analysis of existing work and highlight some concerns regarding the practical use of these control methods. In particular, we critique the use of high knowledge models of algorithm behaviour for shifting the expertise requirement from algorithm development to building models of algorithm behaviour. Furthermore, such models are often brittle, so cannot cope with change or be generalized to other problem domains or algorithms.
The investigation of our thesis applies low knowledge control methods to scheduling algorithms, both search algorithms and large neighbourhood search heuristics, and compares performance against optimal high knowledge algorithm selection methods. We also present a tuning procedure for configuring control systems that combine multiple algorithms. The best performing low knowledge control methods perform well across all problem sets and time limits and do not require significant effort or expertise to implement.
