Aspects of the Structure Problems in Linear Programming

在大规模优化中，由于边界、网络、多周期、分段线性和其他常见结构的出现，人们对识别和利用线性规划中的结构的可能性仍然有着浓厚的兴趣。这项拨款下的研究将利用算法和计算环境方面的最新进展，对结构问题的几个方面提供新的看法。将启动、完成或评价的具体项目包括：大规模分段线性单纯形法的扩展测试，以及分段线性规划内点法的理论和计算研究；内点法的阶梯改编及其在多处理机计算机上的实施；以及基于代数建模语言的线性规划系统中的结构的表示和识别。

Motivated by the occurrence of bounds, networks, multiple periods, piecewise-linearities and other common constructs in large-scale optimization, there continues to be strong interest in the possibilities for identifying and exploiting structures in linear programming. Research under this grant will take advantage of recent advances in algorithms and computing environments to provide a fresh look at several aspects of the structure problem. Specific projects to be initiated, completed or evaluated include extended tests of large-scale piecewise- linear simplex methods, together with theoretical and computational studies of interior-point methods for piecewise- linear programming; staircase adaptations of interior-point methods, and their implementation on multi-processor computers; and the representation and recognition of structures in a linear programming system based on an algebraic modeling language.