On both practical and theoretical levels, linear programming is one of the most important optimization problems studied in Computer Science and Operations Research. But, on both levels, our current understanding of linear programming has substantial room for improvement.
Theoretically, the worst-case time bounds that are known for current algorithms are far higher than what is observed in practice. Although the recent development of smoothed analysis gives polynomial-bounded running time on certain kinds of instances, the bounds are still very high-degree polynomials, much larger than what we see in practice. Our current theoretical models do not accurately model how linear-programming algorithms behave in practice. Practically, current algorithms often take time quadratic in the size of the input (even to find approximate, as opposed to optimal, solutions). An ideal algorithm should take linear, or nearly linear, time. State-of-the-art implementations (such as CPLEX) are generally commercially developed, taking research on them out of the public/academic domain. Effective implementation of Simplex and Interior-Point algorithms is difficult, as evidenced by the performance gap between free and commercial solvers and the cost of the best commercial solvers. To solve very large problems, even the most effective implementations sometimes require manual testing and tuning, and even then can be unpredictably slow.
Existing algorithms leave room for improvement on several fronts, including ease of implementation, ease of use, numerical stability, public accessibility, running time, and good theoretical analyses. Given the widespread practical and commercial importance of linear programming, the development and publication of algorithms with provably good worst-case running times, provable numerical stability, and relatively simple, open-source implementations, have the potential for broad practical and commercial impact. The goal of the project is to make progress in this direction by designing provably fast (nearly linear time) and numerically robust approximation algorithms for very large linear-programming problems. The project focuses on algorithms for so-called mixed packing and covering linear programs --- an important special case in which all coefficients in the constraint matrix are non-negative. In practice, for problem instances having more than thousands of rows and columns, the goal of the project is algorithms that find solutions within 1% of optimal, and do so orders of magnitude more quickly than algorithms now used in practice (Simplex, Interior Point, and Ellipsoid). The algorithms should be numerically stable --- requiring no special treatment of instances with ill-conditioned constraint matrices. The algorithms will be made publically available via implementations and open-source publications.
On both theoretical and practical levels, linear programming is one of the most important optimization problems studied in Computer Science and Operations Research. But there is substantial room for improvement on both levels. Theoretically, our analyses of standard linear-programming algorithms give unrealistically high bounds. Practically, state-of-the-art codes such as CPLEX and Gurobi take a long time (super-linear) on large inputs and rely on proprietary methods, while public-domain algorithms abound but are often even slower and can be numerically unstable. The goal of this project was to design, analyse, and implement approximation algorithms for a special case of linear-programming problems called mixed packing and covering problems. As described in the proposal, the algorithms were to be numerically stable, and were to produce approximate solutions in nearly linear-time. The project accomplised these goals. In addition, it produced several parallel algorithms that can be implemented to run in poly-logarithmic time, requiring only nearly linear total work. The grant resulted in eight publications in peer-reviewed conferences and journals, as well as working implementations (of the sequential algorithms) published in open-source code repositories. For more details on the main results, see ``Nearly Linear-Time Approximation Schemes for Mixed Packing/Covering and Facility-Location Linear Programs'' ( http://arxiv.org/abs/1407.3015 ).
