I’ve just attended a presentation from Thorsten Koch entitled “Which Mixed Integer Programs could a million CPUs solve?” at CPAIOR 2011. Like any presentation of a challenging research topic would be, it has left more doubts than answers at the end of it. Let’s understand part of the rationale of that.
As many people had already noticed, the frequency of individual processors are not increasing any longer due to technological restrictions of the current technology. Instead of that, our computers are having more and more cores. Despite the performance improvement being still noticeable for a standard user which otherwise would have many different applications being handled by the same processor, having more cores does not help a single software if it is not designed to take advantage of that.
In the case of optimization applications, that can be even more dramatic, since solvers like CPLEX does a lot of processing at the root node. Koch suggests that algorithms like the Interior Points Method would gain part of the Simplex share in the future, as is the case of parallel algorithms for matrix factorization. Hence, it seems that algorithm design researchers will have an increased budget in the forthcoming years.