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

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

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.