15-853: Algorithms in the Real World (Guy Blelloch)

next up previous
Topic 3: Linear Programming

[ Topics | Scribe Notes | Readings | Text Books | Links ]

Topic Outline

  • Formulation
  • Related problems (e.g. quadratic programming)
  • Different formulations
  • Dual problem and the duality theorem
  • Geometric interpretation
  • Algorithms
  • Simplex Method
  • Geometric interpration
  • The tableau
  • Using matrices and recent optimizations
  • Ellipsoid method
  • Interior point methods,
  • Centering, projections and Newton's method
  • Affine scaling methods
  • Potential reduction methods (e.g. Karmakar)
  • Central trajectory methods (log barrier)
  • Applications
  • Max flow and min-cost flow.
  • Substep in integer programming.
    • (*) topics will only be covered briefly

    Scribe Notes

  • Linear Programming 1 (draft) (Richard Davis)
  • Linear Programming 2 (Steven Czerwinski)

    • Readings

    These readings will be/have been given out in class.
  • Gilbert Strang. Linear Algebra and its Applications. Third Edition. Chapter 8 (Linear programming and game theory).
    This is the most concise and clear introduction to the simplex method I have read and it also contains a short description of Karmakar's interior-point method. If you have another source you have already used and feel comfortable with, feel free to read it instead.
  • 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.
  • THIS READING HAS BEEN POSPONED TO THE INTEGER PROGRAMMING PAGE 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 Algorithms in the Real World home page.
    Guy Blelloch, guyb@cs.cmu.edu.