Generating cutting planes for mixed integer programming problems in a parallel computing environment

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-grained 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. In particular, the degree of decentralization, as governed by the synchronization schemes, has little effect on the overall quality of the cuts generated.