Experiments with parallel branch-and-bound algorithms for the set covering problem

The authors discuss the results of computational experiments using a new parallel multi-task model for integer optimization. The model is implemented in C on a BBN TC2000 computer. Eight branch-and-bound algorithms based on the use of two types of tasks, linear programming and subgradient optimization with Lagrangean relaxation, are tested on difficult randomly generated set covering problems. The authors investigate the influence of relaxation choice and node selection strategy on parallel performance. Results indicate that the Lagrangean relaxation using a mixed selection strategy is effective on the largest problems. The best overall algorithms divide the computer resources into two distinct searches, which communicate only to update global information on lower and upper bounds.