Low-Knowledge Algorithm Control

Abstract

This paper addresses the question of allocating computational resources among a set of algorithms in order to achieve the best performance on a scheduling problem instance. Our pri-mary motivation in addressing this problem is to reduce the expertise needed to apply constraint technology. Therefore, we investigate algorithm control techniques that make deci-sion based only on observations of the improvement in so-lution quality achieved by each algorithm. We call our ap-proach “low-knowledge ” since it does not rely on complex prediction models. We show that such an approach results in a system that achieves significantly better performance than all of the pure algorithms without requiring additional human expertise. Furthermore the low knowledge approach achieves performance equivalent to a perfect high-knowledge classifi-cation approach.