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.