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.
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.