Advanced Methods for Automated Optimization and Modeling of the Empirical Performance of Highly Parameterized Heuristic Algorithms

硬组合问题在许多对经济和社会都很重要的领域发挥着关键作用，包括正式的硬件和软件验证、决策支持系统、生产和运输计划以及资源管理和分配。在许多情况下，人们认为不存在可证明有效的算法，但启发式方法能够有效地解决实际中出现的这些问题的实例，但传统的启发式算法的设计过程是次优的。它通常涉及一个手动阶段，探索许多算法组件及其参数的组合(所谓的算法配置)，并在基准问题上对它们进行经验评估。人工探索可能配置的组合空间是困难、乏味和耗时的，因此，算法设计者往往不能充分挖掘其高度参数化算法的全部潜力。本项目的主要目标是通过开发完全形式化的计算机辅助算法设计和分析过程来改进这种手动算法设计过程，以帮助人类算法设计者和最终用户充分利用高度参数化算法的灵活性。在之前关于算法配置(AC)的综合工作中--找到高度参数的算法的最佳配置的问题--申请人开发了现有的最好的AC程序。这个项目的部分目标是：(1)进一步大幅提高AC的技术水平；(2)基于自动化的AC程序，构建高性能的算法组合(使用定制的高度参数化的算法的补充配置)；(3)不仅提高算法性能，而且自动通知算法设计者决定其实例经验硬度的特征、决定其算法经验性能的组件以及两者之间的交互作用。作为该项目的一部分，所开发的方法将与领域专家(4)合作，以大幅提高对经济和社会具有相当重要意义的广泛应用的最新水平。这些应用包括正式软件验证(在计算机安全方面的应用)、答案集编程(在决策支持系统中的应用)、混合整数规划(在工业过程和公共交通系统的优化中的应用)、自动计划(在自主机器人和生产和物流计划中的应用)、以及资源管理和分配(在自然资源日益稀缺的时代，这是一个特别重要的问题)。我们将开发的所有自动化程序都将公开提供，以支持领域专家解决更广泛的问题，以推动各自专业领域的最先进水平。

Hard combinatorial problems play a key role in many areas of importance to both the economy and society, including formal hard- and software verification, decision support systems, production & transportation planning, and resource management and allocation. In many cases, provably efficient algorithms are believed not to exist, but heuristic methods are able to solve instances of these problems effectively that occur in practice.However, the traditional design process of heuristic algorithms is suboptimal. It typically involves a manual phase of exploring combinations of many algorithmic components and their parameters (so-called configurations of the algorithm) and empirically evaluating them on benchmark problems. The manual exploration of the combinatorial space of possible configurations is difficult, tedious, and time-consuming, and as a result, algorithm designers often fail to exploit the full potential of their highly parameterized algorithms.The key objective of this project is to improve upon this manual algorithm design process, by developing fully-formalized procedures for computer-aided algorithm design and analysis, that help human algorithm designers and end users take full advantage of the flexibility of highly parameterized algorithms. In comprehensive previous work on algorithm configuration (AC) - the problem of finding the best configuration of highly parameterized algorithms - the applicant developed the best existing AC procedures. These AC procedures already led to substantial advances in the state of the art for solving various hard computational problems.Partial objectives of this project are:(1) to substantially improve the state of the art for AC further;(2) based on automated AC procedures, to construct high-performance algorithm portfolios (using custom-made complementary configurations of highly parameterized algorithms); and(3) to not only improve algorithm performance, but to also automatically inform algorithm designers about characteristics that determine their instances’ empirical hardness, components that determine their algorithms’ empirical performance, and the interaction of the two.The automated procedures to be developed are independent of particular domains and algorithms and can thus be applied flexibly. As part of this project, the developed methods will be applied in collaboration with domain experts(4) to substantially advance the state of the art for a broad range of applications of considerable importance to economy and society.These applications include formal software verification (with applications in computer security), answer-set programming (with applications in decision support systems), mixed integer programming (with applications in the optimization of industrial processes and of public transportation systems), automated planning (with applications in autonomous robots and in production & logistics planning), and resource management & allocation (an especially important problem in an age of ever sparser natural resources).All automated procedures we will develop will be made publically available, to support domain experts in an even broader range of problems to advance the state of the art in their respective area of expertise.