Combinatorial search algorithms are indispensable in many engineering applications, including manufacturing, scheduling, computer-aided design, and operations research. Finding the best approximate solution under given resource constraints is very important, especially for real-time applications. Traditional algorithms either require an impractical amount of time and space to find an optimal solution, or give heuristic solutions with no guarantee on their accuracy. This is not desirable in many critical real-time applications or when large problems are involved.

Research has been focused on studying resource-constrained discrete combinatorial optimization algorithms that find better solutions at the same cost, or algorithms that find solutions of the same quality but at a lower cost.

• Resource-constrained branch-and-bound search. Under space limitations, strategies have been developed for optimally evaluating a search so that the search can complete in the minimum amount of time using a given amount of space. Under space/time limitations, optimal search strategies have been developed and analyzed so that the solutions obtained have the maximum degree of accuracy achievable in given amount of space and time limitations.

• Meta-control in IDA*-style searches. The meta-control provides a framework for designing combinatorial search algorithms. The framework was implemented in Wise, a software package implementing meta-level resource-constrained search and available for distribution.

• Parallel branch-and-bound search. Efficient parallel search algorithms that can achieve linear speedups for a large range of number of processors have been studied. Methods to cope with anomalies of parallelism in combinatorial searches have been developed and analyzed.

• Architectural supports. The distributed-ring concept has been developed to support efficient parallel search on distributed-memory multiprocessor systems.

• Learning heuristics for branch-and-bound search. Machine learning techniques have been applied to learn new strategies for combinatorial search algorithms that are generalizable. Algorithms have been found that perform an order-of-magnitude faster than the best known algorithms for a large number of well-known combinatorial search problems.

• Applications. The main application is in the reordering of (sequential and parallel) Prolog programs for efficient search.