Linear Optimization (01:640:354)

Spring 2008

Quick Overview

Course Content

The purpose of this one-semester-long course is to provide a rather elementary, yet rigorous, treatment of the basic theory and the (not so basic) applications of linear optimization (also known as linear programming) and integer programming, and hence it serves as a good first course in linear optimization. Demonstration of some of the software for modelling and solving linear and integer 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 and integer programming 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: the simplex method and its variations, branch-and-bound and cutting plane methods;
• 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). The textbook has a review chapter of this material, named Chapter 0, and I assume everyone has mastered these topics. 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 Thursday, 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.
• Exercises: I will post a list of practice problems after nearly every class. These are not required to be handed in, and turning them in will not affect your grade. However, these problems will allow everyone to spend as much time practicing the material as they want. I will not post solutions to these problems, but feel free to discuss your solutions with each other, or with me after class or during office hours. Occasionally some of these problems, or very similar ones may appear as homework problems.
• Collaboration and cheating: You are allowed to seek or give help to (or collaborate with) other students on homework assignments. No collaboration of any kind is permitted on midterms and exams.
• Textbooks: The official textbook of the course is Bernard Kolman and Robert E. Beck, Elementary Linear Programming with Applications, 2nd ed., Academic Press, 1995. (ISBN 012417910X). 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), Linear Programming by Vasek Chvatal (ISBN 0716715872), 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.