Lecture Summaries  for COMP 566                     Autumn 2008

      also check:announcements                        return to:course home page

        Linear Programming, V. Chvatal

Sep 2: What is operations research, mathematical programming and linear programming. Read: Review analysis of algorithms extracted from Nielsen & Chuang (you may skip the proof of Thm 3.2): pdf

Sep 4: How to solve a linear program. Read: Text, Ch. 2

Sep 9: Another example and a general description of dictionaries and the simplex method. Redundancy. Some geometry.  Read pp. 250-55
Sep 11: Pivot selection and cycling. Read pp. 27-33.
(Extra material for those interested: For more about cycling take a look here. For more about Zadeh's rule see here and here.)

Sep 16: Initialization. Klee-Minty examples. Read 39-42 and Chapter 4.
Sep 18: Proof of the finiteness of Bland's rule. The Fundamental theorem of linear programming. Read: pp. 37-38,42-43.
Sep 23: Duality. Interpretations of duality. The weak duality theorem. Relationships between outcomes for primal and dual problems. Read: pp. 54-62 (except proof of duality theorem.)
Sep 25,30: Proof of the strong duality theorem and complementary slackness. Economic interpretations. Read: 57-59, 62-68.
Oct 2: Revised simplex method. Read: 97-105

Oct 7: Review of assignments, old exam problems, etc.

Oct 9: First class test.
Oct 14: Review of test. General linear programming (bounds on variables). Read:  118-124
Oct 16,21: Network simplex method. Read ; 291-305
Oct 23: Network applications:  Scheduling production and inventory, napkins and  the transportation problem. Read  320-327, 345
Oct 28: Dual simplex method. Sensitivity analysis. Read class handout Ch 10 and text 148-153.

Oct 30: Integer programming. Read class handout Ch. 11. pdf ppt

Nov 4: Review of assignments, old exams etc.

Nov 6:  Second class test. Material up to and including Oct. 30.
Nov11: Interior point methods (Attendance compulsory). Read class handout,  up to the top of page 9.
Nov 13: Interior point methods. Read: rest of  class handout.
Nov 18, 20, 25, 27: Class presentations. (Attendance compulsory)


return to: course home page