Lecture Summaries  for COMP 566                     Autumn 2007

      also check:announcements                        return to:course home page

Text
        Linear Programming, V. Chvatal

Sep 4  What is operations research, mathematical programming and linear programming.
Sep 6  Formulating a linear program and solving it. Read: Chvatal Chaps. 1,2
Sep 11  More on dictionaries and the simplex method. Pivot selection rules, cycling. Read Ch 3 up to  p. 36.
Sep 13  How to use Maple to solve LPs "by hand". Degeneracy and redundancy. More on geometry of polyhedra.
             Read: pp 250-255, 260-261.
Sep 18: How fast is the simplex method. The Two phase simplex method. Read: pp 39-52
Sep 20: LP duality. Upper bounds on the objective function. The dual LP. Weak duality theorem. Read: pp 54-57

Sep 25: Proof of the strong duality theorem. Complementary Slackness and economic interpretations. Read: pp 57-68

Sept 27: Proof of finiteness of Bland's rule. Finding a solution to a system of inequalities the easy way. Farkas' lemma and certificates of optimality. Read: handout (pdf) also text pp. 37-38.
Oct 2: Revised simplex method. Economic interpretation of revised simplex. Read: pp 97-105, 114-115(pricing and zero tolerances).
Oct 4: Zero sum games. Read Ch. 15.
Oct 9: No class, Monday schedule is used today at Mcgill.
Oct 11: First test  covering material up to and including October 4 lecture.
Oct 16,18,23,25: Introduction to non-zero sum games and LCP.
Readings: Sections 2-5 of (pp 6-22)  doc2,  doc3  ,  pp 1-21 of doc4
                  Bimatrix game formulated as an LCP is given in doc1  (which is an alternative to doc4).
Slides: slides1, slides2, and slides3.

Oct 30: Dual simplex method.  Read: Text or handout, chapter 10.

Nov 1,6: Unimodular matrices, network problems solvable by LP. Bipartite vs non-bipartite matchings. Read: here pp 161-165.
Nov 8: Gomory's cutting plane method. Read: Handout, chapter 11. Assigment 4 posted.
Nov 13, 15: Interior point method. Handout given in class.
Nov 20: Review of homework.
Nov 22: Second class test. Topics  up to and including Nov 8, including all homeworks. Emphasis on material since first test.
Nov 27: Conor on mining. (Attendance compulsory)
Nov 29 & Dec 4: Class presentations. (Attendance compulsory)

          

return to: course home page