Linear Programming

Recommended Readings

  • Gilbert Strang. Linear Algebra and its Applications. Third Edition. Chapter 8 (Linear programming and game theory).
    This is a concise and clear introduction to the simplex method and it also contains a short description of Karmakar's interior-point method.
  • E. L. Johnson and G. L. Nemhauser. Recent developments and future directions in mathematical programming. (abstract).
    This is a good overview of optimization techniques including both linear and integer programming.
  • Robert Freund and Shinji Mizuno. Interior Point Methods: Current Status and Future Directions This is a good overview of interior point methods, and is available online.
  • G. L. Nemhauser. The age of optimization: solving large-scale real-world problems. (abstract).
    This paper has some overlap with the previous paper but concentrates on applications.

    • Recommended Text Books

  • M. Bazaraa, J. Jarvis, and H. Sherali. Linear Programming and Network Flows. Wiley, 1990.
  • Dimitris Bertsimas and John N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997
  • J. P. Ignizio and T. M. Cavalier, Linear Programming. Prentice Hall, 1994
  • G. L. Nemhauser, A.H.G. Rinnooy Kan, and M. J. Todd (ed.). Optimization. Elsevier, 1989.
  • Robert J. Vanderbei. Linear Programming: Foundations and Extensions. Academic Publishers, 1996
    • The linear programming faq has a nice list of textbooks with some annotation.

    Further Readings and Links

  • General links
  • Linear Programming Faq from Argone National Labs. It includes a list of other web links.
  • Operations Research Page by Michael Trick.
  • An on-line Mathematical Programming Glossary by Harvey Greenberg.
  • A course on linear programming and related topics with online course notes.
  • Online Companies that sell linear programming products (see the bottom of the page).
  • A list of journals on operations research.
  • Interior Point Methods.
  • "Interior Point Methods for linear programming: Computational State of the Art", Lustig, Marsten, and Shanno, (abstract.)
    This is a very good overview of interior point methods and Karmakar's algorithm. I suggest it for everyone if you have time.
  • Did Karmarkar deserve a patent? (a discussion)
  • The Interior point archive.
    Lots of useful information and many online papers.
  • Primal-Dual Interior-Point Methods by Stephe Wright. A book on interior-point methods. Contains pointers to available software.
  • Implementing Simplex.
  • Progress in Linear Programming, Robert Bixby, (abstract.)
    This is actually a follow up on the Lustig, Marsten, and Shanno article above. Its basic theme is that we should not give up on Simplex quite so soon.
  • Implementing the simplex method for the Optimization Subroutine Library, Forrest and Tomlin, (abstract.)
    This describes IBM's implementation of Simplex for OSL, a product they sell.
  • Parallel Implementations
  • Dual Simplex on an SGI
  • Applications (typically use Mixed Integer Programming)
  • A page on crew scheduling and transportation problems. This page has many good pointers.
  • Interfaces is a journal dedicated to applications of operations research.
  • A paper on how MIP is used for sports scheduling and in particular the Atlantic Coast Conference basketball official 1997-98 schedule.
  • A list of applications
  • Another list of applications of linear and integer programming for the DELTA airlines, American Airlines, Northwest Airlines, UPS, Coca Cola, and the federal highway commission.
    • Back to the topic list.