Theory of Linear Optimization (16:711:614 and 01:640:453)

Fall 2008

Course Content

The purpose of this one-semester-long course is to provide a fairly complete and rigorous treatment of the fundamental theory and the (not so basic) applications of linear optimization (also known as linear programming) and various network problems, and hence it serves as a good first course in linear optimization for higher level undergraduates as well as for masters students in engineering, computer science or mathematics. Demonstration of some of the software for modelling and solving linear programming problems is included, either in class or in the computer lab.

Upon completion of this course the students can expect to

• be able to formulate mathematical models as linear programming or network optimization problems, and to apply these modelling skills to solve problems in engineering, finance, operations research, economics, the natural sciences, and the like;
• understand some of the commonly used, basic algorithms of linear optimization, including the simplex method and its variations;
• understand the basics of linear programming theory (duality, convex polyhedra);
• have some experience with some of the linear programming solvers available;
• be ready for a multitude of more advanced classes in optimization, including Discrete Optimization, Nonlinear Optimization, Combinatorial Optimization & Network Flows, Scheduling, and other topics in operations research.

General Information

• Prerequisites: Math 250 (Intro to Linear Algebra). Practically this means good understanding of, and the ability to use(!), basic linear algebra notions, such as: matrix and vector notation; notions of linear independence, rank, determinant, and the connection between these terms; inverse of a matrix and ways to compute it; solution of systems of linear equations; relations between linear algebra and geometry (equation of a line, plane, etc). Some background in algorithms, graph theory and other basic computer science material will be very useful at times, but I will not assume that anyone knows anything of this.
• Attendance: I do not take formal attendance, and attendance has no direct effect on your grade. However, most students find regular attendance essential to performing well in the class. Questions are strongly encouraged during class.
• Exams: There will be two in-class midterm exams and a final. All exams will be closed book, but you can bring a one-page handwritten "cheat sheet". The final will be cumulative, covering all topics in the course.
• Homework: I am planning to give about 7-8 homework assignments. Typically, homework assignments will be due in class on Tuesday, the week after they were handed out. There is zero credit for late homework. I will drop your lowest assignment score when computing your overall homework performance, with late or missing assignments counting as a score of zero.
• Textbooks: The official textbook of the course is Vasek Chvatal, Linear Programming, Freeman, 1983. (ISBN 0-7167-1195-8 or 0-7167-1587-2 (pbk)). Occasionally additional material will be handed out in class. Other recommended books are: Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis (ISBN 1886529191), and Combinatorial Optimization by Christos H. Papadimitriou and Kenneth Steiglitz (ISBN 0486402584). These books offer a more rigorous and more comprehensive treatment of linear optimization and integer programming. Use these with care, though: unfortunately some of the notational and naming conventions are different from that of the official textbook, which can be confusing at times.

Grading

The course grade will be based on your aggregate score, combining your scores on all written class work with the following weights:

• 20% Homeworks (excluding the lowest score)
• 20% First midterm
• 20% Second midterm
• 40% Final

If your final is higher than your lower midterm, then the final counts 50%, and the lower midterm only 10%.

The cutoffs for the final letter grades do not come in predetermined places, but will not be higher than 85% for A, 70% for B, 55% for C, and 40% for D.