EFFICIENT COMBINATORIAL SEARCH ALGORITHMS

The search for acceptable solutions in a combinatorially large problem space is an important problem in the fields of artifical intelligence, operations research, and computer science. Ways of improving the efficiency of this search process includes reducing the number of nodes searched by the process and reducing the average time to search each node. One way to reduce the number of nodes searched is to use an appropriate selection scheme. Best-first branch-and-bound (B&B) algorithms generally expand less nodes than depth-first B&B algorithms. However, a best-first B&B algorithm requires exponential memory space. A depth-first B&B algorithm requires linear memory space. In a two-level memory system, this difference in space requirements can cause the average expansion time of each node to differ for the two B&B strategies. This thesis presents results on the efficiency of the B&B strategies in a two-level memory. The best B&B strategy depends on the characteristics of the problem domain as well as the characteristics of the two-level memory. A best-first B&B algorithm should be used when it expands much less nodes than the corresponding depth-first B&B algorithm, and when the secondary memory is very fast. A depth-first B&B algorithm should be used when it expands approximately the same number of nodes as the corresponding best-first B&B algorithm, and when the secondary memory is very slow. The choice for intermediate situations is not so clear. One result of our research is the modified B&B algorithm, which can be used in these intermediate situations. The modified B&B algorithm has been designed to match the characteristics of a two-level memory system. Dominance relations prune unnecessary nodes in search graphs and so reduce the number of nodes searched by the search process. There is no systematic procedure to derive dominance relations because they are problem-dependent. A possible approach to this problem is the use of knowledge-based techniques. This thesis also contains a study of the machine learning of dominance relations. Among the results are a representation for optimization problems that exposes useful domain information, a classification of dominance relations that identifies the useful forms of dominance relations, and the applicable learning mechanisms. This research also includes a study of a system that learns dominance relations by experimentation. A prototype of this system has been able to learn dominance relations for several scheduling and mathematical programming problems