Instructor Reha Tütüncü, WEH 7219, x8-2558, reha+@andrew.cmu.edu

Lectures:MF 8:30-10:20 Posner Hall 146

Office Hours:M 10:30am-12:00pm, Friday 10:30am-12:00pm

Work: periodic HWs(75%), take-home final (25%)

Prerequisites: Basic multivariate calculus, some linear algebra. If in doubt come and talk to me about it.

Homepage: http://www.math.cmu.edu/~reha/856.html

Course Description

This course will present a self-contained treatment of linear programming (LP) theory. We will also discuss solution methods for LPs: After a brief discussion of the simplex method we will focus on interior-point methods (IPMs). The emphasis on IPMs will also bias our view of LP theory. For example, we will discuss LP duality using the notion of the central path, an essential element of many IPMs.

We will discuss complexity issues and demonstrate polynomial complexity of certain IPMs. We will also discuss the worst-case and average-case complexities of the simplex method. We will study sensitivity questions from the alternative viewpoints of the optimal basis and the optimal partition . If time allows, we will discuss a subset of the following topics: Implementation of LP algorithms, column generation, modelling languages for LPs, the ellipsoid method, subexponential pivoting rules for the simplex method.

Course Materials

There is no required textbook for this course. Useful references include Primal-Dual Interior-Point Methods by S. Wright and Theory and Algorithms for Linear Optimization by Roos, Terlaky, and Vial, as well as the Lecture Notes for this course developed and used by Professor John Hooker in 1998. I will distribute my own (most probably hand written) notes at the beginning of each lecture.