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

无论在实际还是理论层面上，线性规划都是计算机科学和运筹学中最重要的优化问题之一。但是，在这两个层面上，我们目前对线性规划的理解都有很大的改进空间。从理论上讲，当前算法已知的最坏情况时间界限远远高于实际观察到的时间界限。虽然最近发展的光滑分析在某些情况下给出了多项式有界的运行时间，但界仍然是非常高的多项式，比我们在实践中看到的要大得多。我们目前的理论模型不能准确地模拟线性规划算法在实践中的行为。实际上，当前的算法通常在输入的大小上花费时间的平方(甚至找到近似的而不是最优的解)。理想的算法应该耗费线性或近线性的时间。最先进的实现(如CPLEX)通常是商业开发的，使对它们的研究走出了公共/学术领域。有效地实现单纯形和内点算法是困难的，自由和商业求解器之间的性能差距和最好的商业求解器的成本就是明证。要解决非常大的问题，即使是最有效的实现有时也需要手动测试和调优，甚至可能会非常慢。现有的算法在几个方面留下了改进的空间，包括易于实现、易于使用、数值稳定性、公众可访问性、运行时间和良好的理论分析。鉴于线性规划的广泛实用和商业重要性，开发和发布具有可证明的良好最坏情况运行时间、可证明的数值稳定性和相对简单的开放源码实现的算法具有广泛的实际和商业影响。该项目的目标是在这个方向上取得进展，为非常大的线性规划问题设计可证明的快速(近线性时间)和数值健壮的近似算法。该项目专注于所谓的混合包装和覆盖线性规划的算法-约束矩阵中所有系数都非负的重要特例。在实践中，对于超过数千行和列的问题实例，该项目的目标是找到最优解的1%以内的算法，并且比实践中使用的算法(单纯形法、内点法和椭球法)更快地找到解决方案。算法应该是数值稳定的-不需要对具有病态约束矩阵的实例进行特殊处理。这些算法将通过实现和开源出版物公开提供。

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.