Mechanistic heuristic problem solving and heuristic search algorithms that exploit phase transitions and backbones

这个项目研究通用启发式问题的解决，通过开发(1)解决组合优化问题的有效策略和算法，以及(2)利用相变的内在问题特征和“主干”--即所有最优解中需要固定的变量--来解决这些问题。这个项目的一般方法是使用数学方法来机械化解决问题。该项目的两个研究主题中的每一个都涉及几个副主题。第一个重点是开发一种通用的启发式问题解决方法，其中包括一套自动开发启发式策略和搜索算法的新方法。它采用了一种使用约束编程范例的表示方案、一组用于推导启发式函数的约束处理方法，以及一种用于自动确定给定问题的启发式函数和搜索方法的正确组合的学习方案。第二个重点是利用固有问题特性，特别是相变和主干。该项目计划考虑各种问题，包括组合优化问题(例如旅行商问题)、约束优化问题(例如调度和资源分配)以及计算生物学中的复杂优化问题(例如序列比对和单倍型推断)。由于可以通过启发式搜索和组合优化来解决各种各样的问题，因此这项研究的结果可能会在计算机科学和其他领域(如运筹学、计算分子生物学)产生非常广泛的影响。

This project studies general purpose heuristic problem solving through development of (1) efficient strategies and algorithms for solving combinatorial optimization problems, and (2) effective methods for exploiting intrinsic problem features of phase transitions and "backbones" -- that is, variables that need to be fixed among all optimal solutions -- to solve these problems. The general approach of this project is to mechanize problem solving using mathematical means. Each of the two research thrusts of the project involves several subtopics. The first thrust is to develop a general approach to heuristic problem solving that involves a new set of methods for automatically developing heuristic strategies and search algorithms. It employs a representation scheme using a constraint programming paradigm, a set of constraint manipulation methods for deriving heuristic functions, and a learning scheme to automatically determine the 'right' combination of heuristic functions and search methods for a given problem. The second thrust focuses on utilizing intrinsic problem features, particularly phase transitions and backbones. The project plans to consider a variety of problems, including combinatorial optimization problems (e.g., the Traveling Salesman Problem), constraint optimization problems (e.g., scheduling and resource allocation), and complex optimization problems in computational biology (e.g., sequence alignment and haplotype inferencing). The results of this research could have a very broad impact in computer science and beyond (e.g., operations research, computational molecular biology) due to the great variety of problems that can be approached through heuristic search and combinatorial optimization.