Introduction: New approaches to linear programming.

*(English)*Zbl 0612.90082This issue of Algorithmica presents papers on various aspects of nonlinear methods for solving linear programming problems, inspired by the work of Karmarkar. This introduction describes some of these aspects and briefly mentions other recent developments in the field. A bibliography of recent articles is included.

##### MSC:

90C05 | Linear programming |

90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |

Full Text:
DOI

##### References:

[1] | K. M. Anstreicher, A monotonic projective algorithm for fractional linear programming,Algorithmica,1 (1986), 483–498. · Zbl 0625.90088 · doi:10.1007/BF01840458 |

[2] | K. M. Anstreicher, A strengthened acceptance criterion for approximate projections in Karmarkar’s algorithm, Report, Yale School of Organization and Management, 1986. · Zbl 0618.90055 |

[3] | I. Adler, M. G. C. Resende, and G. Veiga, An implementation of Karmarkar’s algorithm for linear programming, Report ORC 86-8, Operations Research Center, University of California, Berkeley, CA, 1986. · Zbl 0682.90061 |

[4] | E. R. Barnes, A variation on Karmarkar’s algorithm for solving linear programming problems, Research Report No. RC 11136, IBM T. S. Watson Research Center, Yorktown Heights, NY, 1985. |

[5] | D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming, I: affine and projective rescaling trajectories, AT&T preprint, 1986. |

[6] | U. Betke and P. Gritzmann, Projection algorithms for linear programming, presented at the 1986 AMS-IMS-SIAM Summer Research Conference on Discrete and Computational Geoemtry, Santa Cruz, CA, 1986. |

[7] | C. E. Blair, The iterative step in the linear programming algorithm of N. Karmarkar,Algorithmica,1 (1986), 537–539. · Zbl 0618.90058 · doi:10.1007/BF01840462 |

[8] | L. G. Blum, Towards an asymptotic analysis of Karmarkar’s algorithm, Extended Abstract, 1985. |

[9] | T. M. Cavalier and A. L. Soyster, Some computational experience and a modification of the Karmarkar algorithm, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985. |

[10] | V. Chandru and B. P. Kochar, A class of algorithms for linear programming, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985. |

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

[12] | S. Chen, Computational experience with the Karmarkar algorithm, presented at the Joint National TIMS/ORSA Meeting, Los Angeles, CA, 1986. |

[13] | G. de Ghellinck and J.-Ph. Vial, An extension of Karmarkar’s algorithm for solving a system of linear homogenous equations on the simplex, Discussion Paper No. 8538, C.O.R.E., Catholic University of Louvain, 1985. |

[14] | G. de Ghellinck and J.-Ph. Vial, A polynomial Newton method for linear programming,Algorithmica,1 (1986), 425–453. · Zbl 0629.90058 · doi:10.1007/BF01840456 |

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

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

[17] | P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin, and M. H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, Technical Report SOL 85-11, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA, 1985. · Zbl 0624.90062 |

[18] | D. Goldfarb and S. Mehrotra, A relaxed version of Karmarkar’s method, Technical Report, Department of Industrial Engineering and Operations Research, Columbia University, New York, 1986. · Zbl 0654.90049 |

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

[20] | 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. |

[21] | M. Iri and H. Imai, A multiplicative barrier function method for linear programming,Algorithmica,1 (1986), 455–482. · Zbl 0641.90048 · doi:10.1007/BF01840457 |

[22] | S. Kapoor and P. M. Vaidya, Fast algorithms for convex quadratic programming and multicommodity flows,Proceedings of the 18th Annual ACM Symposium on Theory of Computing, ACM, New York, 1986, pp. 147–159. |

[23] | N. Karmarkar, A new polynomial-time algorithm for linear programming,Proceedings of the 16th Annual ACM Symposium on Theory of Computing, ACM, New York, 1984, pp. 302–311; revised version:Combinatorica,4 (1984), 373–395. · Zbl 0557.90065 |

[24] | N. K. Karmarkar, Further developments in the new polynomial time algorithm for linear programming, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985. |

[25] | N. K. Karmarkar and L. P. Sinha, Application of Karmarkar’s algorithm to overseas telecommunications facilities planning, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985. |

[26] | L. G. Khachiyan, A polynomial algorithm in linear programming,Soviet Math. Dokl,20 (1979), 191–194. · Zbl 0414.90086 |

[27] | M. Kojima, Determining basic variables of optimum solutions in Karmarkar’s new LP algorithm,Algorithmica,1 (1986), 499–515. · Zbl 0661.90057 · doi:10.1007/BF01840459 |

[28] | M. Kojima and K. Tone, An efficient implementation of Karmarkar’s new LP algorithm, Research Report No. B-180, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, 1986. |

[29] | K. O. Kortanek, D. N. Lee, and M. Shi, An application of a hybrid algorithm for semi-infinite programming, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985. |

[30] | O. Mangasarian, Normal solutions of linear programs,Math. Programming Stud.,22 (1984), 206–216. · Zbl 0588.90058 |

[31] | N. Megiddo, A variation on Karmarkar’s algorithm, unpublished manuscript, 1984. |

[32] | N. Megiddo, On the complexity of linear programming, inAdvances in Economic Theory (T. Bewley, ed.), Cambridge University Press, Cambridge (to appear). |

[33] | N. Megiddo, Pathways to the set of optimal solutions in linear programming, IBM Research Report RJ5295, Almaden Research Center, 1986. · Zbl 0612.90082 |

[34] | N. Megiddo and M. Shub, Boundary behavior of interior point algorithms for linear programming, IBM Research Report RJ5319, 1986. · Zbl 0675.90050 |

[35] | G. Mitra, M. Tamiz, J. Yadegar, and K. Darby-Dowman, Experimental investigation of an interior search algorithm for linear programming, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985. |

[36] | K. G. Murty, A new interior variant of the gradient projection method for linear programming, Technical Paper 85-18, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI, 1985. |

[37] | K. G. Murty and Y. Fathi, A feasible direction method for linear programming,Oper. Res. Lett.,3 (1984), 121–127. · Zbl 0544.90070 · doi:10.1016/0167-6377(84)90003-8 |

[38] | J. L. Nazareth, Homotopy techniques in linear programming,Algorithmica,1 (1986), 529–535. · Zbl 0623.90052 · doi:10.1007/BF01840461 |

[39] | M. W. Padberg, A different convergence proof of the projective method for linear programming, Report, New York University, 1985. |

[40] | M. W. Padberg, Solution of a nonlinear programming problem arising in the projective method for linear programming, Report, New York University, 1985. |

[41] | P. F. Pickel, Implementing the Karmarkar algorithm using simplex techniques, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985. |

[42] | P. F. Pickel, Approximate projections for the Karmarkar algorithm, I, Theory, Report, Polytechnic Institute of New York, Farmingdale, NY, 1985. |

[43] | J. Renegar, A polynomial-time algorithm, based on Newton’s method, for linear programming, Report MSRI 07118-86, Mathematical Sciences Research Institute, Berkeley, CA, 1986. · Zbl 0654.90050 |

[44] | G. Rinaldi, A projective method for linear programming with box-type constraints,Algorithmica,1 (1986), 517–527. · Zbl 0627.90062 · doi:10.1007/BF01840460 |

[45] | D. F. Shanno and R. E. Marsten, On implementing Karmarkar’s algorithm, Working Paper, Graduate School of Administration, University of California, Davis, CA, 1985. |

[46] | M. J. Todd and B. P. Burrell, An extension of Karmarkar’s algorithm for linear programming using dual variables,Algorithmica,1 (1986), 409–424. · Zbl 0621.90048 · doi:10.1007/BF01840455 |

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

[48] | R. J. Vanderbei, M. S. Meketon, and B. A. Freedman, A modification of Karmarkar’s linear programming algorithm,Algorithmica,1 (1986), 395–407. · Zbl 0626.90056 · doi:10.1007/BF01840454 |

[49] | Y. Ye,K-Projection and the cutting-objective methods for linear programming, presented at the 12th Symposium on Mathematical Programming, Cambridge, MA, 1985. |

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.