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

硬组合问题在经济和社会的许多重要领域发挥着关键作用，包括正式的硬件和软件验证，决策支持系统，生产和运输计划以及资源管理和分配。在许多情况下，可证明的有效算法被认为是不存在的，但启发式方法能够有效地解决在实践中发生的这些问题的实例。然而，传统的启发式算法的设计过程是次优的。它通常涉及一个手动阶段，探索许多算法组件及其参数（所谓的算法配置）的组合，并在基准问题上对它们进行经验评估。手工探索可能配置的组合空间是困难的、乏味的和耗时的，因此，算法设计者经常不能充分利用其高度参数化算法的潜力。该项目的主要目标是通过开发计算机辅助算法设计和分析的完全形式化程序来改进这种手动算法设计过程，从而帮助人类算法设计者和最终用户充分利用高度参数化算法的灵活性。在对算法配置（AC）（寻找高度参数化算法的最佳配置的问题）的综合先前工作中，申请人开发了现有的最佳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.