Very large-scale linear programming: A case study in exploiting both parallelism and distributed memory

There has been limited success with parallel implementations of both the simplex method and interior point methods for solving real-world linear programs. Experience with a parallel implementation of CPLEX, a state of the art implementation of the simplex method, on an Intel distributed-memory multiprocessor machine will be described. We will exploit the structure of the class of problems arising from airline crew scheduling. A particular instance with 12,753,313 variables will be studied. This instance is too large to fit on current sequential machines in standard linear programming data structures. We will show how our implementation exploits both distributed memory and parallelism and allows the full problem to be kept in memory. Finally, we will discuss algorithmic ideas that our implementation affords us and show results for a variant of the greatest decrease algorithm, an idea suggested many years ago but never tested on linear programming problems of significant size