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