Parallel Branch-and-Bound Algorithms for General Mixed Integer Programming on the CM-5

• DOI: 10.1137/0804046
• Publication Date: 2005-02-23T13:02:14Z
• Authors: Jonathan Eckstein
• Keywords: Branch and bound; Branch and cut; Workstation

This "proof of concept" paper describes parallel solution general mixed integer programs by a branch-and-bound algorithm on the CM-5 multiprocessing system. It goes beyond prior work implementing reasonably realistic general-purpose programming algorithm, as opposed to specialized method for narrow class problems. shows how use capabilities produce an efficient implementation employing centrally controlled search, achieving near-linear speedups using 64–128 processors variety difficult problems derived from real applications. In concrete terms, problem requiring half hour solve SPARC-2 workstation might be solved in 15–20 seconds, and originally taking week reduced about hour. Central search control does have limitations, some final computational experiments begin address merits more decentralized options.