An extension of Karmarkar’s algorithm for linear programming using dual variables. (English) Zbl 0621.90048

Todd, Michael J.; Burrell, Bruce P.

Algorithmica 1, 409-424 (1986).

The 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.

Reviewer: F.Plastria

MSC:

90C05	Linear programming
65K05	Numerical mathematical programming methods
90C06	Large-scale problems in mathematical programming

Keywords:

duality; Karmarkar’s algorithm; dual solutions; extreme point solutions; OR factorizations

References:

[1]	Anstreicher, K. M., Analysis of Karmarkar’s algorithm for fractional linear programming, Manuscript (1985), New Haven, CT: School of Organization and Management, Yale University, New Haven, CT
[2]	Charnes, A.; Cooper, W. W., Programming with linear fraction functionals, Naval Res. Logist. Quart., 9, 181-186 (1962) · Zbl 0127.36901 · doi:10.1002/nav.3800090303
[3]	Charnes, A.; Song, T.; Wolfe, M., An explicit solution sequence and convergence of Karmarkar’s algorithm, Manuscript (1984), Austin, TX: University of Texas at Austin, Austin, TX
[4]	Chvatal, V., Linear Programming (1983), New York and San Francisco: Freeman, New York and San Francisco · Zbl 0537.90067
[5]	Frisch, K. R., The logarithmic potential method of convex programming, unpublished (1955), Oslo: University Institute of Economics, Oslo
[6]	Gay, D., A variant of Karmarkar’s linear programming algorithm for problems in standard form, Manuscript (1985), Murray Hill, NJ: AT&T Bell Laboratories, Murray Hill, NJ
[7]	George, A.; Heath, M. T., Solution of sparse linear least squares problems using Givens rotations, Linear Algebra Appl., 34, 69-83 (1980) · Zbl 0459.65025 · doi:10.1016/0024-3795(80)90159-7
[8]	Gill, P. E.; Murray, W.; Saunders, M. E.; Tomlin, J. A.; Wright, M. H., On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, Manuscript (1985), Stanford, CA: Department of Operations Research, Stanford University, Stanford, CA
[9]	Golub, G. H.; Van Loan, C. F., Matrix Computations (1983), Baltimore: The Johns Hopkins Press, Baltimore · Zbl 0559.65011
[10]	Gonzaga, C., A conical projection algorithm for linear programming, Manuscript (1985), Berkeley, CA: Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA
[11]	Haimovich, M., The simplex method is very good! On the expected number of pivot stops and related properties of random linear programs, Manuscript (1983), New York: Graduate School of Business, Columbia University, New York
[12]	Heath, M., Some extensions of an algorithm for sparse linear least squares problems, SIAM J. Sci. Statist. Comput., 3, 223-237 (1982) · Zbl 0483.65027 · doi:10.1137/0903014
[13]	Huard, P.; Abadie, J., Resolution of mathematical programming with nonlinear constraints by the method of centers, Nonlinear Programming, 207-219 (1967), Amsterdam: North-Holland, Amsterdam
[14]	Jensen, D.; Steger, A., Private communication (1985), Stonybrook, New York: Department of Applied Mathematics and Statistics, State University of New York at Stonybrook, Stonybrook, New York
[15]	Kallio, M.; Porteus, E. L., A class of methods for linear programming, Math. Programming, 14, 161-16 (1978) · Zbl 0371.90099 · doi:10.1007/BF01588963
[16]	Karmarkar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065 · doi:10.1007/BF02579150
[17]	Megiddo, N., A variation on Karmarkar’s Algorithm, Manuscript (1985), San Jose, CA: IBM Research Laboratory, San Jose, CA
[18]	Todd, M. J., Extensions of Lemke’s algorithm for the linear complementarity problem, J. Optim. Theory Appl., 20, 397-416 (1976) · Zbl 0327.90018 · doi:10.1007/BF00933128
[19]	Tomlin, J. A., An experimental approach to Karmarkar’s projective method for linear programming, Manuscript (1985), Mountain View, CA: Ketron Inc., Mountain View, CA