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.
