Efficient BranchandBound Search
Combinatorial search algorithms are indispensable in many engineering
applications, including manufacturing, scheduling, computeraided
design, and operations research. Finding the best approximate
solution under given resource constraints is very important,
especially for realtime 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 realtime
applications or when large problems are involved.
Research has been focused on studying resourceconstrained
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.

Resourceconstrained branchandbound 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.

Metacontrol in IDA*style searches.
The metacontrol provides a framework for designing combinatorial
search algorithms. The framework was implemented in
Wise,
a software package implementing metalevel
resourceconstrained search and available for
distribution.

Parallel branchandbound 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 distributedring concept has been developed to
support efficient parallel search on distributedmemory
multiprocessor systems.

Learning heuristics for branchandbound 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 orderofmagnitude faster than the
best known algorithms for a large number of wellknown
combinatorial search problems.

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