Exploiting special structure in Karmarkar's linear programming algorithm

We propose methods to take advantage of specially-structured constraints in a variant of Karmarkar's projective algorithm for standard form linear programming problems. We can use these constraints to generate improved bounds on the optimal value of the problem and also to compute the necessary projections more efficiently, while maintaining the theoretical bound on the algorithm's performance. It is shown how various upper-bounding constraints can be handled implicitly in this way. Unfortunately, the situation for network constraints appears less favorable.Research supported in part by National Science Foundation Grant ECS-8602534, ONR Contract N00014-87-K-0212 and the US Army Research Office through the Mathematical Sciences Institute of Cornell University.