The steepest descent gravitational method for linear programming (Q583105)

This paper presents a new approach to solving linear programming problems based on the search of descent gravitational directions. This method can be viewed as a special method of feasible directions. It has several advantages over other LP methods: (1) Karmarkar's method requires an effort to transform the linear program into Karmakar's canonical form. (2) The descent gravitational method considers, at each step, only a small subset of all the constraints, the so called ``touching constraints'' as defined by a special definition pertinent to this method. In this way only a small subset of the constraints, the active constraints, is analyzed. (3) The major part of the computational efforts is devoted to the search of the direction to move and redundant constraints never enter into this computation. (4) Nondegeneracy assumptions are not required for the proof of finite convergence of the method. (5) All ``interior points'' methods require a final procedure, based on a pivot method, to convert the near optimum solution to the ``true optimum'' solution. This method does not need any expensive final procedure similar to this, but it gives the actual primal optimum solution. If a dual solution is required it needs only a few additional computations.