An extension of Karmarkar’s algorithm for linear programming using dual variables.

*(English)*Zbl 0621.90048The recent, but already classic projective algorithm of Karmarkar for linear programs is an interior point method, i.e. it generates a sequence of relative interior points of the feasible region, thereby reducing the objective value by a fixed factor. With an all integer problem the process may thus be stopped after a polynomial number of steps and the optimal solution obtained by rounding. The algorithm does however not generate dual solutions, of great importance in practice.

This paper describes a variant of Karmarkar’s method in which both primal and dual solutions are generated, converging to optimal primal and dual solutions respectively. The method applies when the optimal value of the problem is unknown, and has the same convergence properties as Karmarkar’s. Details on efficient implementation using OR factorizations indicate the complexities of the calculations involved at each step, and shows how extreme point solutions may be derived at each step with minor additional work.

This paper describes a variant of Karmarkar’s method in which both primal and dual solutions are generated, converging to optimal primal and dual solutions respectively. The method applies when the optimal value of the problem is unknown, and has the same convergence properties as Karmarkar’s. Details on efficient implementation using OR factorizations indicate the complexities of the calculations involved at each step, and shows how extreme point solutions may be derived at each step with minor additional work.

Reviewer: F.Plastria

##### MSC:

90C05 | Linear programming |

65K05 | Numerical mathematical programming methods |

90C06 | Large-scale problems in mathematical programming |

PDF
BibTeX
XML
Cite

\textit{M. J. Todd} and \textit{B. P. Burrell}, Algorithmica 1, 409--424 (1986; Zbl 0621.90048)

Full Text:
DOI

##### References:

[1] | K. M. Anstreicher, Analysis of Karmarkar’s algorithm for fractional linear programming, Manuscript, School of Organization and Management, Yale University, New Haven, CT, 1985. |

[2] | A. Charnes and W. W. Cooper, Programming with linear fraction functionals,Naval Res. Logist. Quart.,9 (1962), 181–186. · Zbl 0127.36901 · doi:10.1002/nav.3800090303 |

[3] | A. Charnes, T. Song, and M. Wolfe, An explicit solution sequence and convergence of Karmarkar’s algorithm, Manuscript, University of Texas at Austin, Austin, TX, 1984. |

[4] | V. Chvatal,Linear Programming, Freeman: New York and San Francisco, 1983. |

[5] | K. R. Frisch, The logarithmic potential method of convex programming, unpublished, University Institute of Economics, Oslo, 1955. |

[6] | D. Gay, A variant of Karmarkar’s linear programming algorithm for problems in standard form, Manuscript, AT&T Bell Laboratories, Murray Hill, NJ, 1985. |

[7] | A. George and M. T. Heath, Solution of sparse linear least squares problems using Givens rotations,Linear Algebra Appl.,34 (1980), 69–83. · Zbl 0459.65025 · doi:10.1016/0024-3795(80)90159-7 |

[8] | P. E. Gill, W. Murray, M. E. Saunders, J. A. Tomlin, and M. H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, Manuscript, Department of Operations Research, Stanford University, Stanford, CA, 1985. · Zbl 0624.90062 |

[9] | G. H. Golub and C. F. Van Loan,Matrix Computations, The Johns Hopkins Press, Baltimore, 1983. · Zbl 0559.65011 |

[10] | C. Gonzaga, A conical projection algorithm for linear programming, Manuscript, Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA, 1985. |

[11] | M. Haimovich, The simplex method is very good! On the expected number of pivot stops and related properties of random linear programs, Manuscript, Graduate School of Business, Columbia University, New York, 1983. |

[12] | M. Heath, Some extensions of an algorithm for sparse linear least squares problems,SIAM J. Sci. Statist. Comput.,3 (1982), 223–237. · Zbl 0483.65027 · doi:10.1137/0903014 |

[13] | P. Huard, Resolution of mathematical programming with nonlinear constraints by the method of centers, inNonlinear Programming (J. Abadie, ed.), North-Holland, Amsterdam, 1967, pp. 207–219. |

[14] | D. Jensen and A. Steger, Private communication, Department of Applied Mathematics and Statistics, State University of New York at Stonybrook, Stonybrook, New York, 1985. |

[15] | M. Kallio and E. L. Porteus, A class of methods for linear programming,Math. Programming,14 (1978), 161–16. · Zbl 0371.90099 · doi:10.1007/BF01588963 |

[16] | N. Karmarkar; A new polynomial time algorithm for linear programming,Combinatorica,4 (1984), 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150 |

[17] | N. Megiddo, A variation on Karmarkar’s Algorithm, Manuscript, IBM Research Laboratory, San Jose, CA, 1985. · Zbl 0561.90063 |

[18] | M. J. Todd, Extensions of Lemke’s algorithm for the linear complementarity problem,J. Optim. Theory Appl.,20 (1976), 397–416. · Zbl 0327.90018 · doi:10.1007/BF00933128 |

[19] | J. A. Tomlin, An experimental approach to Karmarkar’s projective method for linear programming, Manuscript, Ketron Inc., Mountain View, CA, 1985. · Zbl 0634.90044 |

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.