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

# Topic 3: Linear Programming

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