Algorithm Engineering for NP-Complete Problems

该项目将研究先进的组合算法技术和数据结构对启发式搜索性能的影响，无论是在理论上还是在构建通用组合优化引擎的背景下。该引擎将应用于实践中常见的20个np完全问题的启发式生成质量实现。这种方法的重点是识别通用的高性能局部优化方法。此外，它提出了各种新的理论研究路线，这将导致改进的优化算法。本研究的影响围绕着(1)开发新的组合算法和数据结构，支持强大的交叉、突变和循环避免操作，以及映射能量景观，以及可证明的良好近似；(2)系统地研究局部搜索变体的性能，包括模拟退火、遗传算法和禁忌搜索；(3)开发用于研究、工业、以及教育应用，以及(4)创建一个新的竞争性论坛来评估算法工程的最新技术。

This project will study the impact that advanced combinatorial algorithmtechniques and data structures can have on the performance ofheuristic search, both in theory and in the context ofbuilding a general-purpose combinatorial optimization engine.This engine will be applied to yield quality implementations ofheuristics for twenty NP-complete problems which arise commonly in practice.This approach focuses attention on identifying versatile high-performanceapproaches to local optimization. Further, it suggests a variety ofnew lines of theoretical research which will lead to improved optimizationalgorithms.The impact of this research revolves around (1) the development of newcombinatorial algorithms and data structures supporting powerfulcrossover, mutation, and cycle-avoidance operations, and mapping energylandscapes, as well as provably good approximations, (2) a systematicstudy of the performance of local search variants including simulatedannealing, genetic algorithms, and tabu search, (3) the development ofuseful software for research, industrial, and educational applications,and (4) the creation of a new competitive forum for assessing the stateof the art in algorithm engineering.