iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/BF01582888
Interior point algorithms for linear programming with inequality constraints | Mathematical Programming Skip to main content
Springer Nature Link
Log in

Interior point algorithms for linear programming with inequality constraints

  • Published:
Mathematical Programming Submit manuscript

Abstract

Interior methods for linear programming were designed mainly for problems formulated with equality constraints and non-negative variables. The formulation with inequality constraints has shown to be very convenient for practical implementations, and the translation of methods designed for one formulation into the other is not trivial. This paper relates the geometric features of both representations, shows how to transport data and procedures between them and shows how cones and conical projections can be associated with inequality constraints.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. I. Adler, N. Karmarkar, M. Resende and G. Viega, “An implementation of Karmarkar's algorithm for linear programming,”Mathematical Programming 44 (1989).

  2. K. Anstreicher, “A monotonic projective algorithm for fractional linear programming,”Algorithmica 1 (1986) 483–498.

    Google Scholar 

  3. E. Barnes, D. Jensen and Chopra, “A polynomial-time version of the affine-scaling algorithm,” Manuscript, New York University (New York, 1988).

    Google Scholar 

  4. R.M. Freund, “An analog of Karmarkar's algorithm for inequality constrained linear programs, with a “New” class of projective transformations for centering a polytope,” Sloan Working Paper No. 1921-87, Massachusetts Institute of Technology (Cambridge, 1987).

    Google Scholar 

  5. P. Gill, W. Murray, M. Saunders, J. Tomlin and M. Wright, “On projected newton barrier methods for linear programming and an equivalence to Karmarkar's projective method,”Mathematical Programming 36 (1986) 183–209.

    Google Scholar 

  6. C. Gonzaga, “An algorithm for solving linear programming problems in O(n 3 L) operations,” in: N. Megiddo, ed.,Progress in Mathematical Programming: Interior-Point and Related Methods (Springer, New York, 1988).

    Google Scholar 

  7. C. Gonzaga, “Conical projection algorithms for linear programming,”Mathematical Programming 43 (1988) 151–173.

    Google Scholar 

  8. C. Gonzaga, “Polynomial affine algorithms for linear programming,”Mathematical Programming 49 (1990) 7–21.

    Google Scholar 

  9. C. Gonzaga, “Search directions for interior linear programming methods,” Memorandum UCB/ERL M87/44, Electronics Research Laboratory, University of California (Berkeley, CA, 1987), to appear inAlgorithmica.

    Google Scholar 

  10. M. Iri and H. Imai, “A multiplicative penalty function method for linear programming,”Algorithmica 1 (1986) 455–482.

    Google Scholar 

  11. N. Karmarkar, “A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.

    Google Scholar 

  12. M. Todd and B. Burrell, “An extension of Karmarkar's algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424.

    Google Scholar 

  13. H. Yamashita, “A polynomially and quadratically convergent method for linear programming,” Manuscript, Mathematical Systems Institute, Inc. (Tokyo, Japan, 1986).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. COPPE, Federal University of Rio de Janeiro, P.O. Box 68511, 21945, Rio de Janeiro, RJ, Brazil

    Clovis C. Gonzaga

Authors
  1. Clovis C. Gonzaga
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gonzaga, C.C. Interior point algorithms for linear programming with inequality constraints. Mathematical Programming 52, 209–225 (1991). https://doi.org/10.1007/BF01582888

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01582888

Key words

Search

Navigation