Algorithms and hardware for the solution of set partitioning problems

This thesis is concerned with an integer linear programming problem, called the set partitioning problem. The problem is: minimize cx, subject to Ax=e, where A is a binary matrix, e is a column of ones, and c is a cost vector. Despite its particularly simple structure, the set partitioning problem has practical applications in many different areas. There are many applications, however, for which the set partitioning problem is so large and difficult that it cannot be solved in a reasonable amount of time. The binary structure of the partitioning problem suggests that special digital hardware could be developed to solve these problems more efficiently. Two new algorithms, one that could exploit such hardware, are presented and evaluated in this thesis. They are similar in that they use the same bounding procedure. The first is a branch-and-bound algorithm, and the second uses the more sophisticated A* [16] branching strategy. Comparisons with one of the better set partitioning algorithms in the literature indicates that the new algorithms perform significantly better. Heuristic versions of the A* algorithm are also investigated. The heuristic algorithms promise good sub-optimal solutions to very large partitioning problems. A hybrid algorithm formed by combining the A* algorithm with the branch-and-bound algorithm is shown to yield optimal solutions to large problems in minimal time. To solve partitioning problems the generalized design of a microprocessor based system, supplemented with special hardware, is investigated. Such a system would be organized as a peripheral device attached to the host computer. It would be cost effective because it would allow the solution of very large partitioning problems without using the expensive resources of a mainframe computer. Such a system should be of interest to those in application areas that require the solution of many large partitioning problems.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat