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.