The steepest descent gravitational method for linear programming

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.

Recommendations

Cites work

Cited in

(16)

Describes a project that uses

Uses Software

MINOS

This page was built for publication: The steepest descent gravitational method for linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q583105)