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.