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.