Mathematical Programming Computation, Volume 10, Issue 2, June 2018

Font Size:  Small  Medium  Large

mplrs: A scalable parallel vertex/facet enumeration code

David Avis, Charles Jordan

Abstract


We describe a new parallel implementation, mplrs, of the vertex enumer- ation code lrs that uses the MPI parallel environment and can be run on a network of computers. The implementation makes use of a C wrapper that essentially uses the existing lrs code with only minor modifications. mplrs was derived from the earlier parallel implementation plrs, written by G. Roumanis in C++ which runs on a shared memory machine. By improving load balancing we are able to greatly improve performance for medium to large scale parallelization of lrs. We report computational results comparing parallel and sequential codes for vertex/facet enu- meration problems for convex polyhedra. The problems chosen span the range from simple to highly degenerate polytopes. For most problems tested, the results clearly show the advantage of using the parallel implementation mplrs of the reverse search based code lrs, even when as few as 8 cores are available. For some problems almost linear speedup was observed up to 1200 cores, the largest number of cores tested. The software that was reviewed as part of this submission is included in lrslib-062.tar.gz which has MD5 hash be5da7b3b90cc2be628dcade90c5d 1b9.


Full Text: PDF

mpc footer
© MPS 2008-2018