CRPC-TR95554: Parallel Mixed Integer Programming

Robert Bixby, William Cook, Alan Cox, Eva Lee

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.