Constraint Branch-and-Bound Method for Set Partitioning Problems.

摘要

This thesis compares the efficiency of a constraint branch-and-bound method against the conventional variable branch-and-bound method in solving set partitioning problems. Because of the difficulties encountered in writing the constraint branch-and-bound subroutine, it was necessary to solve each subproblem encountered from scratch. This is in contrast to the variable branching code which, when solving closely related subproblems, essentially starts from an advanced starting solution. Even using an inefficient implementation, the constraint branch-and-bound method appears to be significantly more efficient than the conventional variable branch-and-bound method. It saves, on average, 30.0% in CPU time over the variable branch-and-bound-method when tested on a set of small test problems. On average, constraint branch and bound produces 59.3% fewer nodes in its enumeration trees than does variable branch and bound, and the trees encountered are shallower and better balanced. (kr)