A team of researchers from Argonne National Laboratory and the University of Edinburgh have received the 2013 COAP Best Paper Prize for their work in applied mathematics.
“Parallel distributed-memory simplex for large-scale stochastic LP problems.” The paper, which appeared in the international journal Computational Optimization and Applications (COAP), was chosen by the editorial board from more than 90 entries. An article about the award-winning paper is featured in the October 2014 online issue of the journal.
The problem originated in an application involving optimization of complex energy systems under uncertainty, namely, finding cost-optimal and operationally feasible dispatches for electricity generators in the Illinois power grid under large penetration of wind power, which is highly volatile and cannot be accurately predicted in advance, as shown in Fig. 1. The Argonne team initially developed an approach based on interior-point methods that successfully solved large-scale LPs; but it had difficulty efficiently solving a sequence of continuous problems.
“We hoped to use an existing code from which we could develop an efficient, parallel, dual simplex solver. But we quickly concluded that we would have to write such a solver from scratch,” said Lubin, who spent a year in Argonne’s Mathematics and Computer Science Division where this work was performed.
Efficiency and scalability were two main concerns. A communication-reducing parallel product form update strategy was devised to enable scalability; additionally, block hyper-sparsity was exploited to ensure efficiency. Moreover, the implementation benefited from recent advances in high-performance computing architectures to gain additional efficiency.
The award-winning paper was previously acknowledged by the Computational Infrastructure for Operations Research (COIN-OR) project with the award of the COIN-OR INFORMS 2013 Cup.
The research is part of the work being performed in M2ACS: Multifaceted Mathematics for Complex Energy Systems project, supported by the U.S. Department of Energy Advanced Scientific Computing Research Program.
For further information see “Parallel distributed-memory simplex for large-scale stochastic LP problems,” M. Lubin, J. A. J. Hall, C. G. Petra, M. Anitescu, Computational Optimization and Applications (2013) 55(3):571-596.