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.