Lecture Summaries  for COMP 566A                     Autumn 2004

      also check:announcements                        return to:course home page

Text
        Linear Programming, V. Chvatal

Sept 2:  Introduction to Mathematical programming, Operations research and course goals. Formulations of "the tragedy of the commons"
Sept 7: How to solve LPs in standard form. Read ch 2 of the text. Make up and solve one complete example by hand !
Sept 9:  The simplex method in terms of dictionaries. Dantzig and Bland's pivot selection rule. Examples of cycling. Read Ch. 3  up to p.38.
                (A nice treatment of the lexicographic ratio test  is contained in Ignizio & Cavalier, Linear Programming, pp118-122, on reserve in Schulich library.)
Sept 14: Geometry of the simplex method. Degeneracy in polyhedra. Klee -Minty examples of worst case behaviour for Dantzig's rule.
                 Read text: Ch. 4  and pp. 250-260.
Sept 16: Initialization of the simplex method. Introduction to duality. Read Remainder of Ch. 3 and  pp  54-57.
             Optional: Another way of getting a feasible solution to a system of inequalities is described here.

Sept 21: Duality theory. Proofs of the weak and strong duality theorems. Read:  Ch 5 up to p. 62.
Sept 23: Complementary slackness. Economic interpretations of duality.  Proof of the finiteness of Bland's rule. Read: Rest of Ch 5. Also pp. 37-8 Thm 3.3
Sept 28: Introduction to Revised Simplex method. How to avoid taking the inverse of the basis matrix.
Sept 30: An example of Revised Simplex. Eta factorization of the basis matrix. Deriving Farkas lemma from phase 1 of the Simplex Method. Read: Ch. 7 and pp143-5.
Oct 5: General LP problems: how to handle bounded variables. Duality for LPs not in standard form. Read: Ch 8, pp118-124 and C h. 9 (except proof of duality theorem).
Oct 7: Review. Test will cover all of the above material.
Oct 12: First class test.
Oct 14: Review of test. The dual simplex method. Introduction to  integer programming. Read: Text,  Ch 10 up to p.153.
Oct 19: Gomory's cutting plane algorithm for integer programming. Read: class handout.
Oct 21: Zero sum games. LP formulation and minmax theorem.  Read: Text, Chapter 15
Oct 26: Non-zero sum games and Nash equilibria. Read: First 10 pages of von Stengel's survey here. Supplemental notes here.
Oct 28: Basic information on vertex enumeration can be found in text pp. 271-275.  The approach given in class is based on my paper  (Read up to the end of Prop. 3.1.).
              A tutorial on reverse search is contained in the paper. (will not be covered in test.)
Nov 2,4: Introduction to primal dual interior point methods. Read: Class handout. Second class test on Nov 11 covers all material up to Nov 4 lecture.

Nov 9: Review, Nash games again.
Nov 11: Second Class test.
Nov 16, 18: More on interior point methods: convergence, feasibility regions, barrier methods.
Nov 23, 25, 30: Class presentations. Attendance compulsory!

                 return to: course home page