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.
