Operational Parameterization for Heuristics (OPERAH)

实际中出现的许多计算问题都是NP难的。由此推测，这些问题不可能在所有输入实例上都能有效地解决。针对困难问题的一种理论驱动的算法设计方法是参数化算法。这里的目的是通过利用典型输入数据的结构来获得高效的算法。该结构由取决于输入数据的数值参数来描述。然后，在参数具有较小值的那些输入上，参数化算法是快速的。对于某些问题，参数化算法可能会导致最先进的实现。然而，在选择启发式方法的实践中，它们很少使用。两种非常重要的启发式方法是局部搜索和贪婪启发式。OPERAH项目旨在了解如何使用参数化算法来进一步改进局部搜索和贪婪启发式。研究的重点是所谓的运行参数。它们不是由输入结构确定的，而是由算法的用户选择的。操作参数描述了更长的运行时间和更好的解决方案质量之间的权衡：增加参数值可以改善解决方案，同时增加运行时间。因此，用户通过选择参数值来限制运行时间，并获得相应性质的解。通过这种类型的参数化，我们的目标是缓解参数化算法的缺点，即现实世界中的输入数据对于经典参数通常具有较大的参数值。通过这种方式，我们的目标是增加参数化算法的实用潜力。更具体地说，目的是研究几个重要优化问题的操作参数化范型。对于每一种算法，他们的目标要么是开发用于参数化局部搜索的高效算法，要么是开发所谓的贪婪启发式加速算法，或者证明这些算法与计算机科学中的标准猜想相矛盾。开发的算法将被实现，并与最先进的启发式算法进行实验比较。在这些研究中，我们特别旨在评估上述运行时间和解决方案质量之间的权衡。

Many computational problems arising in practice are NP-hard. It is thus conjectured that these problems cannot be solved efficiently on all input instances. A theory-driven approach to algorithm design for hard problems is parameterized algorithmics. Here, the aim is to obtain efficient algorithms by exploiting the structure of typical input data. This structure is described by a numerical parameter depending on the input data. Parameterized algorithms are then fast on those inputs where the parameter has a small value. Parameterized algorithms may lead to state-of-the art implementations for some problems. Nevertheless, they are seldom used in practice where heuristics are the method of choice. Two very important heuristic approaches are local search and greedy heuristics.The project Operational Parameterization for Heuristics (OPERAH) aims at understanding how parameterized algorithms can be used to further improve local search and greedy heuristics. The focal point of the studies are so-called operational parameters. These are not determined by input structure but rather chosen by the user of the algorithms. Operational parameters describe a trade-off between higher running times and better solution quality: increasing the parameter value improves the solution while increasing the running time. Thus, the user limits the running time by choosing the parameter value and obtains a solution of the corresponding quality.With this type of parameterization, we aim to mitigate a drawback of parameterized algorithms, the fact that real-world input data often has large parameter values for classic parameters. In this way, we aim to increase the practical potential of parameterized algorithmics. More concretely, the aim is to study the paradigm of operational parameterization for several important optimization problems. For each, the goal is to either develop efficient algorithms for parameterized local search or the so-called turbocharging of greedy heuristics or to show that such algorithms contradict standard conjectures in computer science. The developed algorithms will be implemented and compared experimentally with state-of-the-art heuristics. In these studies, we particularly aim at assessing the above-mentioned trade-off between running time and solution quality.