IE 513 Linear Programming Fall 2001

• Linear Programming by V. Chvatal
• An introduction to complexity, polyhedral theory and combinatorial optimization by G. Dahl
• Lecture notes by R. Weber (ps)

     Topics to be covered:

1.    Generalities on Linear Algebra
2.    Statement and Geometry of the Linear Programming Problem, Some Properties
3.    Applications from Structural Design, Electrical Engineering, Control Theory ..
4.    Duality Theory, Theorems of the Alternative
5.    Applications from Finance
6.    Sensitivity Analysis
7.    Solution of Linear Programs by the Primal Simplex Method
8.    Large Scale Issues, Column Generation, Dantzig-Wolfe and Benders' Decomposition
9.    The Dual Simplex Method
10.    The Ellipsoid Method
11.    Network Flow Problems; Network Simplex, Max-Flow Min-Cut Theorem ...

In addition to those, the students are expected to acquire basic skills in using the AMPL modeling language. For general information see AMPL's site. You can find a library of  ampl solution models here.

 

---

Homeworks:	40 % Homework #1 is here. Due date: October  8, 2001. Homework #2 is here. Due date: October 17, 2001. Homework #3 is here. Due date: October 30, 2001. Last year I assigned 3 hws from the pool of problems. Their solution files are posted here: hw1, hw2, hw3, and a fourth extra hw4(questions and solutions). The final examination and solution can be downloaded here as well.
Midterm Test:	30 % Date: November 5, 2001 (postponed to 14.11.2001).
Final:	30 % Date: January 9, 2002 .

                                   1.11.2001:  First homework graded! Can be picked from my office along with solution sheet.
                                    2.11.2001: Second homework graded and ready to be picked up along with solution sheet.
                                    6.11.2001: Third hw expected to be graded and ready by friday, the 9.11.2001
                                    7.01.2002: Fourth hw graded, can be picked from TA's office,