Model-based Configuration of Algorithms for Solving Hard Computational Problems

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

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.