The 9th edition of the 2013 COIN-OR INFORMS Cup was won by a paper on the parallelization of the revised simplex method for stochastic optimization by Miles Lubin, Julian Hall, Cosmin Petra and Mihai Anitescu. The paper, “Parallel distributed-memory simplex for large-scale stochastic LP problems,” was previously published in the Journal of Computational Optimization and Applications (COAP) and tackles with the challenges of parallelizing the revised simplex method for stochastic linear programming (LP) problems. The computational approach of the paper exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance memory-distributed supercomputers.The novel analysis of the linear algebra and novel parallel scheme for the applying product-form updates for dual block-angular problems make the implementation (PIPS-S) competitive with existing open-source simplex solvers; in addition it achieves significant speed-up when run in parallel.
The paper was selected to enter the competition because COIN-OR linear algebra libraries, in particular CoinFactorization class, sit at the foundation of PIPS-S parallel linear algebra. This was possibly only by looking deeply into the CoinFactorization code, which was found as an “especially difficult task” by the COIN-OR Cup judges. The official announcement and more information can be found on the COIN-OR INFORMS Cup website.