Analytics & Optimization The Algorithm that Runs the World
“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...