The Algorithm that Runs the World

By Qi Huangfu

“The algorithm that runs the world” – says the cover story of a 2012 issue of the NewScientist Magazine. And yes, it is talking about the simplex method.

While the theoretical idea behind the simplex algorithm is relatively simple, how to efficiently implement it in practice is more complex, and has been a major topic for research. Looking back at its history of how the theory evolved, ever since its introduction by George Dantzig in the 1940s,  there have been new ground-breaking research published roughly every decade, with the latest one being Hall and McKinnon’s hyper-sparsity algorithm around the 2000s. However, the simplex world has been relatively quiet since that publication, as if hyper-sparsity is the final brick to the well-polished simplex building.

Inspecting the situation more carefully, the simplex research has never stopped. A highly active direction is parallelization. In the last 20 years, there have been lots of simplex parallelization attempts, from massively distributed machines to modern GPUs, using either dense or sparse matrix computations. However, good speedup ratios are related to less efficient sequential implementations of the simplex method. As a result, the overall performance of these parallelization efforts is still inferior when compared to world-leading sequential simplex solvers.

A meaningful simplex parallelization has to be designed and developed based on a state-of-the-art sequential simplex solver and still allow for significant parallelization. This has been achieved in the most recent version of our optimization suite. As the first commercial parallel simplex solver, it achieves speedup to a factor of two on various large-scale problems.

The key idea behind this implementation is to create more parallelizable scope by combining multiple simplex iterations into one meta simplex iteration. In order to implement this efficiently, several innovative techniques had to be developed. A detailed introduction to this approach is available here. The implementation in our optimization suite is an adaption and further development of this key idea.

After 70 years, we are finally realizing the promise of the algorithm that runs the world.