Generating Cutting Planes for Mixed Integer Programming Problems in a Parallel Computing Environment

摘要

Vparallel 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 ain-tumor research, various strategies of cut synchronization are considered, and their influence on speedup, rrumjinication overhead, load balance, and effectiveness in closing the integrality gap are studied. The parallel .tting-plane algorithm is coupled with an LP-based heuristic to assist in returning a good quality integer asible solution upon termination of the parallel process. The parallel implementation is sufficiently coarse-ained to yield an average of less than 6% of the total time performing tasks associated with communication rerhead, and it provides reasonable speedup when executing in parallel. Noticeable differences in load-balance ores are observed, depending on the number of processors used, the synchronization scheme used, and the ru.ctu.re of the MIP problem instance. Nevertheless, the synergism of the combined collection of cuts generated cally on each processor is effective in closing the integrality gap in all cases, and there is minimal variability the amount of the gap closed as the number of processors varies. In particular, the degree of decentralization, governed by the synchronization schemes, has little effect on the overall quality of the cuts generated.