### 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