Model-based Configuration of Algorithms for Solving Hard Computational Problems

计算机科学及其应用中的许多问题在计算上是困难的。更有效地解决这些问题的进展直接有利于许多研究领域，如调度，生产计划和优化，计算机辅助设计，软件验证和可持续管理。许多硬计算问题的最佳性能算法具有各种参数（如数值阈值和算法组件之间的离散选择）。算法设计者以及这种算法的最终用户经常遇到的问题是选择参数设置，该参数设置使给定的一组问题实例上的一些经验性能度量（例如运行时间或解决方案成本）最小化。算法）来解决该算法配置（AC）问题。基于近年来在优化重要问题的各种算法方面取得的巨大进展，AC的研究在过去几年中得到了迅速的发展。序贯基于模型的优化（SMBO）迭代拟合这些模型，并使用它们来选择下一步要研究的参数设置;模型也可以用于量化参数的重要性，以及参数和实例特征之间的相互作用。我们建议进一步大幅改进SMBO，以创建下一代自动AC方法。特别地，我们的目标是（1）扩展和改进SMBO以处理一般AC问题：（2）减少求解AC方法的计算需求;（3）解决现有技术无法解决的重要相关问题（无模型）AC方法。我们相信，这条研究路线将极大地促进科学研究和设计高性能算法来解决困难的计算问题，并因此在广泛的重要应用中发挥关键作用。

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.