AF: Small: Nearly Linear-Time Algorithms for Mixed Packing and Covering Linear Programs

点击翻译按钮获取中文摘要

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.