Efficient Branch-and-Bound Search
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.