Model-based Configuration of Algorithms for Solving Hard Computational Problems

点击翻译按钮获取中文摘要

Many problems in computer science and its applications are computationally hard. Progress in solving these problems more effectively directly benefits many research areas, such as scheduling, production planning and optimization, computer-aided design, software verification, and sustainable management.The best-performing algorithms for many hard computational problems have various parameters (such as numerical thresholds and discrete choices between algorithm components). A problem routinely encountered by algorithm designers as well as end-users of such algorithms is to select parameter settings that minimize some empirical performance measure (such as runtime or solution cost) on a given set of problem instances.Various research communities have developed automated methods (i.e., algorithms) for solving this algorithm configuration (AC) problem. Based on considerable recent progress in optimizing various algorithms for important problems, research in AC has rapidly been gaining momentum over the last few years.One promising AC approach is based on predictive models of algorithm performance. Sequential model-based optimization (SMBO) iterates between fitting such models, and using them to choose which parameter settings to investigate next; the models can also be used to quantify parameter importance, as well as interactions between parameters and instance characteristics.We propose to substantially improve SMBO further to create the next generation of automated AC methods. In particular, we aim to (1) extend and improve SMBO to handle general AC problems; (2) reduce the computational demands of methods for solving AC; and (3) address important related problems that cannot be handled by existing (model-free) AC methods.We believe that this line of research will greatly facilitate the scientific study and design of high-performance algorithms for solving hard computational problems, and thus play a key role in a wide range of important applications.