Learning Objective:As a beginning graduate course, the first goal is to teach the students the skills to formulate real-world problems as linear programs, and solve them using the available software. The second goal is to teach the students the theoretical principles of linear optimization.
Description:Linear programming problems arise pervasively in science and engineering. The students will be taught to use the available linear programming software to solve real world problems. They will also obtain a broad exposure to the theoretical underpinnings of linear optimization. Prior exposure to optimization is not necessary.
Topics Covered:Introduction; classification of optimization problems; formulation of linear and integer programs; using available software to solve linear programs; geometry of 2-dimensional linear programs; Simplex method: basic feasible solutions, pivoting, degeneracy, cycling and anti-cycling pivot rules, phase I and phase II algorithms; duality; sensitivity analysis; introduction to computational complexity; ellipsoid method; interior point methods; network flow problems.
Applied / Theory:
Homework:Six to eight assignments, assigned roughly every two weeks, may be downloaded from the course web page; the assignments will count for approximately 50% of the course grade.
Exams:Two midterm exams worth approximately 25% of the course grade each. There will be no final exam.
Textbooks:Official textbook information is now listed in the Schedule of Classes. NOTE: Textbook information is subject to be changed at any time at the discretion of the faculty member. If you have questions or concerns please contact the academic department.
Recommended: Linear Programming 1: Introduction (v.1) by George B. Dantzig and Mukund N. Thapa, Springer Series in Operations Research and Financial Engineering, 1997.