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.