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.