论文标题
通过优化编程，改善随机本地搜索以最大顶点重量集团问题的性能
Improving the Performance of Stochastic Local Search for Maximum Vertex Weight Clique Problem Using Programming by Optimization
论文作者
论文摘要
最大顶点权重问题（MVWCP）是对具有广泛现实世界应用的最大集团问题（MCP）的重要概括。在不需要严格保证解决方案最佳性的情况下，通常使用随机局部搜索（SLS）算法解决MVWCP，这也定义了解决此问题的最新技术。但是，没有单个SLS算法可以在所有类别的MVWCP实例中提供最佳性能，并且有效地确定每类MVWCP实例最合适的算法是一项挑战。在这项工作中，我们遵循通过优化（PBO）进行编程范式，以开发一种新的，灵活的和高度参数的SLS框架来求解MVWCP，首次结合了广泛的有效启发式机制。通过自动配置此PBO-MWC框架，我们在最新的求解MVWCP方面取得了重大进展，该框架在广泛的突出基准中，包括两个来自移植医学（肾脏交换）和研究卓越评估的现实世界中应用的两个。
The maximum vertex weight clique problem (MVWCP) is an important generalization of the maximum clique problem (MCP) that has a wide range of real-world applications. In situations where rigorous guarantees regarding the optimality of solutions are not required, MVWCP is usually solved using stochastic local search (SLS) algorithms, which also define the state of the art for solving this problem. However, there is no single SLS algorithm which gives the best performance across all classes of MVWCP instances, and it is challenging to effectively identify the most suitable algorithm for each class of MVWCP instances. In this work, we follow the paradigm of Programming by Optimization (PbO) to develop a new, flexible and highly parametric SLS framework for solving MVWCP, combining, for the first time, a broad range of effective heuristic mechanisms. By automatically configuring this PbO-MWC framework, we achieve substantial advances in the state-of-the-art in solving MVWCP over a broad range of prominent benchmarks, including two derived from real-world applications in transplantation medicine (kidney exchange) and assessment of research excellence.
