I.E. 2082: LINEAR OPTIMIZATION 
(Spring 2002)

INSTRUCTOR:

LECTURES:

TEXT:

There is no required text. The first reference by Bertsimas and Tsitsiklis is an excellent, modern text and is  strongly recommended for those who want to buy one; it is reasonably priced and available at the bookstore. Lecture notes (in the form of copies of all overheads) are required - these will be made available for purchase at the IE office.

REFERENCES:

1. Introduction to Linear Optimization, by Bertsimas and Tsitsiklis.
2. Linear Programming and Network Flows, by Bazaraa, Jarvis, and Sherali.
3. Linear Optimization and Extensions, by Fang and Puthenpura.
4. Linear Programming Foundations and Extensions, by Robert Vanderbei.
5. Optimization Theory for Large Systems, by Leon Lasdon.
6. Applied Mathematical Programming, by Bradley, Hax and Magnanti.
7. Operations Research: Applications and Algorithms, by Wayne Winston.

PREREQUISITES:

1. Introductory course in Linear Programming/Operations Research and familiarity with the simplex algorithm.
2. Knowledge of (a) linear algebra, (b) differential calculus, and (c) basic mathematical concepts such as sets, functions, vectors, matrices etc.
3. An interest in mathematical methods.

CONTENT:

This is a Ph.D./advanced Master's level course meant for students who have already had an introduction to linear programming and the simplex method (typically, as part of an introductory operations research or management science course). It will examine some of the more advanced topics in this area. The primary emphasis will be on concepts and methodology (as opposed to formal theorems and proofs or specific applications of LP). However, a certain amount of requisite theory will be covered. The (tentative) list of topics includes the following: review of the simplex method; the revised simplex method; pricing and pivot selection mechanisms; generalized bounds; product form of the inverse; L-U factorization; duality and postoptimality analysis; dual simplex and primal-dual algorithms; separable programming; Dantzig-Wolfe decomposition; column generation; semi-infinite and generalized linear programming; computational issues and analysis; interior-point methods including affine scaling and path-following algorithms. This list may be expanded or shortened depending on time constraints. Students are expected to make extensive use of the references in addition to the lecture notes.

GRADING: