Lecture Summaries  for COMP 566A                     Autumn 2005

      also check:announcements                        return to:course home page

Text
        Linear Programming, V. Chvatal

Sept 1    No class

Sept 6: Introduction to Mathematical Programming, and a quick outline of the history of Linear Programming. We discussed the fundamental contributions of George Dantzig,  and Leonid Khachiyan, both of whom passed away this year.

Sept 8: How to solve LPs in standard form. Read ch 2 of the text. Make up and solve one complete example by hand !

Sept 13: A formal statement of the simplex method. Dantzig and Bland's rule. Cycling and degeneracy. A geometric view of the simplex method. Read: text ch. 3 except pp 34-38.

Sep 15: Another simple and self contained way of getting a feasible solution to a system of inequalities was described. We proved finiteness and Farkas' lemma. Read:  notes.

Sept 20: Certificates for the 3 termination conditions. Unbounded solutions. Duality theory. Proof of the weak  duality theorems. Read:  Ch 5 up to p. 62 except proof of thm 5.1.

Sep 22: Proof of Strong duality theorem. Interpretation of dual variables. Read: Proof of Thm 5.1 and pp. 65-68.

Sep 27: Complementary slackness conditions. Formulation of 2-layer graph layout as an integer program. Read: pp 62-68 and for graph layout the paper of Junger et al.

Sep 29. The revised simplex method. Read text: Ch 7 to p. 105.

Oct 4. Worst case of the simplex method, Klee-Minty examples. Interpretation of dual and complementary slackness for the diet problem. Read: Ch. 4.

Oct 6: Matrix factorization. Revised simplex methos and complementary slackness. Read: rest of Ch. 7.
           The first class test will be based on the above material.
Oct. 11:  Review problems

Oct. 13: First class test.

Oct. 18: Guest lecturer: Antoine Deza. "Combinatorial Optimization:  Problems and Algorithms "

Oct. 20: Dual simplex method. Read Chvatal 148-156.

Oct. 25: Integer Programming via cutting planes. Read: Class handout.

Oct. 27: Network Simplex method. Read Chvatal ch. 19 up to p. 307. Assignment 3 posted.

Nov. 1: Matrix games. Zero sum games and the min-max theorem. Read text, pp228-233.

Nov. 3.  Non-zero sum games and Nash equilibria. Read:  Notes here.

Second class test contains all material up to and including Nov. 3.
Emphasis on material since first test.
 
Nov. 8,10 Primal-dual interior point method. Read: Class notes.

Nov. 15  Wrap up.

Nov 17: Second class test.

Nov 22,24,29 Class presentations. Attendance compulsory!

                 return to: course home page