Optimization without Round-off Errors

Recently, a NSF grant is awarded to Erick Moreno-Centeno on Optimization without Round-off Errors. It will be thrilling in the community since round-off erros have been a serious concern to solve large scale optimization problems, especially those with integer variables.

This Early-concept Grant for Exploratory Research (EAGER) provides funding to further develop an algorithm to solve systems of linear equations with a specific advantage over Gaussian Elimination in that the algorithm does not have round-off errors. The algorithm will be tailored and adapted to be used within existing optimization algorithms. The key property of the algorithm being further developed is that it maintains the integrality of the numbers throughout its execution. In particular, although the algorithm does contain divisions (which is crucial for the polynomial-time complexity of the

algorithm) all the divisions have a remainder of zero. A detailed complexity analysis of the algorithm will be performed; specifically, both its running time and the number of bits required to represent the numbers throughout the algorithm's execution will be investigated. A modification of the algorithm to perform LU factorizations will also be studied. Finally, the algorithm will be adapted to enable its use for the basis updates performed in state-of-the-art implementations of the revised simplex method.

If successful, the outcomes of this research will lead to a deeper understanding of computational linear algebra free of round-off errors and the associated applications within optimization algorithms. In the linear programming (LP) context, this research will enable us to solve large-scale LPs exactly; this, in turn, will significantly improve the accuracy and speed of integer programming solvers. In addition, since solving systems of linear equations is a critical subroutine of many numerical algorithms, this research will impact many application areas where linear systems frequently arise, including economics, physics, chemistry, and engineering.