Linear Programming: Condition, Knowledge & Complexity

复杂性理论是计算机算法的基础。该理论的目标是制定衡量各种算法的有效性和效率以及各种问题的难度的标准。术语“复杂性”指的是计算所需的资源量。在这个建议中，运行时间或算术运算的数量是主要的资源。本研究旨在进一步发展线性规划（LP）的复杂性理论。特别是，我们分析了决定LP问题难易程度的“条件”数，并使用部分知识对问题进行了“先决条件”。因此，我们研究某些类型的部分知识是否有助于解决这个问题，以及它们如何影响问题的复杂性。如果这些知识有用且可用，那么经验丰富的LP问题实例所有者可能能够使用这些知识更有效地解决问题。总的来说，在开发求解大规模优化问题的高效算法方面取得进展，对于提高制造系统、通信网络、飞机路线、多流程操作和资源规划的效率将具有重要意义。加强这一领域的研究将有助于提高国家在产业竞争力和科学知识方面的利益。企业，无论大小，都使用LP模型来优化电信网络，调度流量，控制制造过程，计划金融投资，最大限度地降低生产成本等。LP已经成为应用最广泛的数学和计算工具。从历史上看，LP的研究进展极大地扩大了其应用范围。许多15年前“无法解决”的问题，现在可以在几分钟内实时解决。该项目的预期结果和发现将进一步加强和改进LP算法的理论结果和实际性能，并可能导致针对各种计算问题的新的高性能算法的发展。

Yinyu Ye Complexity theory is the foundation of computer algorithms. The goal of the theory is to develop criteria for measuring effectiveness and efficiency of various algorithms and difficulty of various problems. The term ``complexity'' refers to the amount of resources required by a computation. In this proposal, running time or number of arithmetic operations is the major resource of interest. The aim of the proposal is to further develop the complexity theory of linear programming (LP). In particular, we analyze ``condition'' numbers that determine the degree of difficulty of an LP problem, and ``precondition'' the problem using Partial Knowledge. Therefore, we study whether or not certain kinds of partial knowledge could help in solving this problem and how they impact the complexity of the problem. If such knowledge is helpful and available, then an experienced owner of LP problem instances might be able to use it to solve them more effectively. In general, progress in the area of developing efficient algorithms for solving large-scale optimization problems will be of great importance in improving the efficiency of manufacturing systems, communication networks, aircraft routing, multiple-flow operations, and resources planning. Strengthening research in this area will contribute to the national interest in industrial competitiveness and scientific knowledge. Businesses, large and small, use LP models to optimize telecommunication networks, to schedule traffic flows, to control manufacturing processes, to plan financial investments, to minimize production costs, etc. LP has been the mostly used applied mathematics and computation tool. Historically, research developments on LP have dramatically widened the scope of its applications. Many problems, which were "unsolvable" 15 years ago, are now solved in few minutes and in real time. The anticipated findings and discoveries resulting from this proposed project will strengthen and improve theoretical results and practical performance of LP algorithms further, and may lead to the development of new high-performance algorithms for a variety of computational problems.