Eva K. Lee
February 1999
A parallel implementation of a disjunctive cutting-plane algorithm in a distributed memory environment is described. Guided by a selection of difficult instances from MIPLIB and real instances obtained from brain tumor research, various strategies of cut synchronization are considered, and their influence on speedup, communication overhead, load-balance and effectiveness in closing the integrality gap are studied. The parallel cutting plane algorithm is coupled with an LP-based heuristic to assist in returning a good quality integer feasible solution upon termination of the parallel process. The parallel implementation is sufficiently coarse-grain to yield an average of less than 6% of the total time performing tasks associated with communication overhead, and it provides reasonable speedup when executing in parallel. Noticeable differences in load-balance scores are observed, depending on the number of processors used, the synchronization scheme used, and the structure of the MIP problem instance. Nevertheless, the synergism of the combined collection of cuts generated locally on each processor is effective in closing the integrality gap in all cases, and there is minimal variability in the amount of the gap closed as the number of processors varies.
Key words: Parallelism, Mixed integer programming, Cutting planes, Disjunctive Cuts, Lift-and-Project.