\input zb-basic
\input zb-ioport
\iteman{io-port 00519589}
\itemau{Rushmeier, Russell A.; Nemhauser, George L.}
\itemti{Experiments with parallel branch-and-bound algorithms for the set covering problem.}
\itemso{Oper. Res. Lett. 13, No.5, 277-285 (1993).}
\itemab
Summary: We 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 Lagrangian relaxation, are tested on difficult randomly generated set covering problems. We investigate the influence of relaxation choice and node selection strategy on parallel performance. Results indicate that the Lagrangian 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.
\itemrv{~}
\itemcc{}
\itemut{parallel processing; set covering; parallel multi-task model; integer optimization; branch-and-bound algorithms; subgradient optimization; Lagrangian relaxation}
\itemli{doi:10.1016/0167-6377(93)90050-Q}
\end