Parallelizing the revised simplex method: Is it time to give up?

Contributed talk at ICCOPT 2013, Lisbon, Portugal: 1st August 2013

J. A. J. Hall


This talk reviews the outcomes of recent work on parallelizing the revised simplex method by Hall and co-workers. Despite their best efforts, and other attempts over the past 25 years, very little progress has been made on developing worthwhile parallel implementations of the revised simplex method for general large-scale sparse LP problems. Indeed, current HPC architecture trends and continuing developments in serial simplex techniques have reduced the scope for progress towards this general goal. Reasons for this will be discussed. However, this talk will describe some successes with HPC simplex implementations for particular classes of problems and for large dense LP problems. Also, a by-product of studying the simplex method with a view to exploiting parallelism has been the development of novel serial techniques and a deeper understanding of the phenomenon of hyper-sparsity and its promotion.