##
**The steepest descent gravitational method for linear programming.**
*(English)*
Zbl 0691.90051

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.

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.

Reviewer: M.Dalla Mora

### Keywords:

redundant constraints; descent gravitational directions; feasible directions; touching constraints### Software:

MINOS
PDF
BibTeX
XML
Cite

\textit{S. Y. Chang} and \textit{K. G. Murty}, Discrete Appl. Math. 25, No. 3, 211--239 (1989; Zbl 0691.90051)

Full Text:
DOI

### References:

[1] | Adler, I.; Resende, M.G.C.; Veiga, G., An implementation of Karmarkar’s algorithm for linear programming, () |

[2] | Anstreicher, K.M., Linear programming and the Newton barrier flow, (1987), Yale University New Haven, CT |

[3] | Barnes, E.R., A variation of Karmarkar’s algorithm for solving linear programming problems, Math. programming, 36, 174-182, (1986) · Zbl 0626.90052 |

[4] | Best, M.J.; Ritter, K., Linear programming: active set analysis and computer programs, (1985), Prentice-Hall Englewood Cliffs, NJ · Zbl 0575.90033 |

[5] | Chiu, S.S.; Ye, Y., Simplex method and Karmarkar’s algorithm: A unifying structure, (1985), EES Department, Stanford University Stanford, CA |

[6] | Chung, S.J.; Murty, K.G., Polynomial bounded ellipsoid algorithm for convex quadratic programming, (), 439-485 |

[7] | Dantzig, G.B., Linear programming and extensions, (1963), Princeton University Press Princeton, NJ · Zbl 0108.33103 |

[8] | Fathi, Y., Computational complexity of LCP’s associated with positive definite symmetric matrices, Math. programming, 17, 335-344, (1979) · Zbl 0421.90072 |

[9] | Fathi, Y., Comparative study of the ellipsoid algorithm and other algorithms for the nearest point problem, () |

[10] | de Ghellinck, G.; Vial, J.P., A polynomial Newton method for linear programming, Algorithmica, 1, 425-453, (1986) · Zbl 0629.90058 |

[11] | Gilbert, E.G.; Johnson, D.W.; Keerthi, S.S., A fast procedure for computing the distances between complex objects in three space, (1986), Aerospace Engineering, University of Michigan Ann Arbor, MI, Tech. Rept. |

[12] | Gill, P.E.; Murrary, W.; Saunders, M.A.; Tomlin, J.A.; Wright, M., On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, () · Zbl 0624.90062 |

[13] | Gill, P.E.; Murrary, W.; Saunders, M.A.; Tomlin, J.A.; Wright, M., A note on nonlinear approaches to linear programming, () |

[14] | Goffin, J.L., Variable metric relaxation methods, part I: A conceptual algorithm, () · Zbl 0545.65045 |

[15] | Gonzaga, C.C., An algorithm for solving linear programming problems in O(_{n}3L) operations, (1987), Department of Electrical Engineering and Computer Sciences, University of California Berkeley, CA |

[16] | Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065 |

[17] | Kojima, M.; Mizuno, S.; Yoshise, A., A primal-dual interior point algorithm for linear programming, () · Zbl 0708.90049 |

[18] | Mangasarian, O.L., Nonlinear programming, (1969), McGraw-Hill New York · Zbl 0194.20201 |

[19] | Monma, C.L., Recent breakthroughs in linear programming methods, (1987), Bell Communicatons Research Murray Hill, NJ |

[20] | Monma, C.L.; Morton, A.J., Computational experience with a dual affine variant of Karmarkar’s method for linear programming, (1987), Bell Communications Research Murray Hill, NJ · Zbl 0627.90065 |

[21] | Murtagh, B.A.; Saunders, M.A., MINOS 5.0 User’s guide, () |

[22] | Murty, K.G., Linear and combinatorial programming, (1976), Krieger Publishing Company Malabar, FL · Zbl 0634.90037 |

[23] | Murty, K.G.; Fathi, Y., A critical index algorithm for nearest point problems on simplicial cones, Math. programming, 23, 206-215, (1982) · Zbl 0479.90077 |

[24] | Murty, K.G., Linear programming, (1983), Wiley New York · Zbl 0634.90037 |

[25] | Murty, K.G., The gravitational method for linear programming, Opsearch, 23, 206-214, (1986) · Zbl 0616.90039 |

[26] | Murty, K.G., Linear complementarity, linear and nonlinear programming, (1988), Heldermann Berlin, F.R.G · Zbl 0634.90037 |

[27] | Renegar, J., A polynomial-time algorithm, based on Newton’s method, for linear programming, () · Zbl 0618.65038 |

[28] | Rosen, J.B., The gradient projection method for nonlinear programming, part I: linear constraints, SIAM J. appl. math., 8, 181-217, (1960) · Zbl 0099.36405 |

[29] | Rosen, J.B., The gradient projection method for nonlinear programming, part II: nonlinear constraints, SIAM J. appl. math., 9, 514-553, (1961) · Zbl 0231.90048 |

[30] | Tamura, A.; Takehara, H.; Fukuda, K.; Fujishige, S.; Kojima, M., A dual interior primal simplex method for linear programming, (1987), Department of Information Sciences, Tokyo Institute of Technology Tokyo, Tech. Rept. |

[31] | Todd, M.J.; Burrell, B.P., An extension of Karmarkar’s algorithm for linear programming using dual variables, Algorithmica, 1, 409-424, (1986) · Zbl 0621.90048 |

[32] | Vanderbei, R.J.; Meketon, M.S.; Freedman, B.A., A modification of Karmarkar’s linear programming algorithm, Algorithmica, 1, 395-408, (1986) · Zbl 0626.90056 |

[33] | Wilhelmsen, D.R., A nearest point algorithm for convex polyhedral cones and applications to positive linear approximation, Math. comp., 30, 48-57, (1976) · Zbl 0326.65024 |

[34] | Wolfe, P., Algorithm for a least distance programming problem, Math. programming study, 1, 190-205, (1974) |

[35] | Wolfe, P., Finding the nearest point in a polytope, Math. programming, 11, 128-149, (1976) · Zbl 0352.90046 |

[36] | Ye, Y., Barrier-projection in projective algorithm for linear programming, (1985), Engineering Economic Systems Department, Stanford University Stanford, CA, Manuscript |

[37] | Ye, Y., Cutting-objective and scaling method: ‘simple’ polynomial algorithm for linear programming, (1985), Engineering Economic Systems Department, Stanford University Stanford, CA, Manuscript |

[38] | Ye, Y.; Tse, E., A polynomial-time algorithm for convex quadratic programming, (1986), Engineering Economic Systems Department, Stanford University Stanford, CA, Manuscript |

[39] | Ye, Y., Karmarkar’s algorithm and the ellipsoid method, Oper. res. lett., 6, 4, 177-182, (1987) · Zbl 0631.90035 |

[40] | Zikan, K.; Cottle, R.W., The box method for linear programming: part I: basic theory, () |

[41] | Zoutendijk, G., Methods of feasible directions: A study in linear and nonlinear programming, (1960), Elsevier New York · Zbl 0097.35408 |

[42] | Zoutendijk, G., Some algorithms based upon the principle of feasible directions, (), 93-121 · Zbl 0254.90050 |

[43] | Zoutendijk, G., Mathematical programming methods, (1976), North-Holland Amsterdam · Zbl 0337.90036 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.