Parallel Mixed Integer Programming

Eva K. Lee, Robert E. Bixby, William Cook, and Alan Cox

June 30, 1995

Abstract:

Numerical experiments for a parallel implementation of a branch-and-bound mixed 0/1 integer programming code are presented. Among its features, the code includes cutting-plane generation at the root node, and employs a new branching-variable selection rule within the search tree. The code runs on a loosely-coupled cluster of workstations using TreadMarks as the parallel software platform. Numerical tests were performed on all mixed 0/1 MIPLIB instances as well as two previously unsolved MIP instances, one arising from telecommunication networks and the other a multicommodity flow problem.

Keywords: Parallelism; Mixed Integer Programming

Abbreviated title: Parallel MIP Solver

Lee, School of Industrial and Systems Engineering, Georgia Institute of Technology, GA 30332-0205. Supported in part by postdoctoral fellowship from the Center for Research on Parallel Computation, and by NSF/NATO grant GER-9452935, NSF CAREER grant 9501584

Bixby, Department of Computational and Applied Mathematics, Rice University, Houston, Texas. Supported in part by the Center for Research on Parallel Computation, Rice University, and by NSF Grants CCR-881504 and CCR-9407142

Cook, Department of Computational and Applied Mathematics, Rice University, Houston, Texas.

Cox, Department of Computer Sciences, Rice University, Houston, Texas. Supported in part by the Texas Advanced Technology Program, Grant 003604-012, and by NSF NYI Award CCR-9457770

Eva Lee
Sun Jan 28 03:53:19 EST 1996