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

#

Topic 3: Linear Programming

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

(*) topics will only be covered briefly
Linear Programming 1 (draft) (Richard Davis)
Linear Programming 2 (Steven Czerwinski)
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.
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.

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