## Lecture Summaries for COMP
566A
Autumn 2005

* also check:*announcements*
return to*:course home page

**Text**

Linear Programming, V.
Chvatal

Sept 1 No class

Sept 6: Introduction to Mathematical Programming, and a quick outline
of the history of Linear Programming. We
discussed the fundamental contributions of George
Dantzig, and Leonid
Khachiyan, both of whom passed away this year.

Sept 8: How to solve LPs in standard form. Read ch 2 of the text. Make up and solve one
complete example by hand !

Sept 13: A formal statement of the simplex method. Dantzig and
Bland's rule. Cycling and degeneracy. A geometric view of the simplex
method. Read: text ch. 3 except pp 34-38.

Sep 15: Another simple and self contained way of getting a feasible
solution to a system of inequalities was described. We proved
finiteness
and Farkas' lemma. Read: notes.

Sept 20: Certificates for the 3 termination conditions. Unbounded
solutions. Duality theory. Proof of the weak duality theorems.
Read:
Ch 5 up to p. 62 except proof of thm 5.1.

Sep 22: Proof of Strong duality theorem. Interpretation of dual
variables. Read: Proof of Thm 5.1 and pp. 65-68.

Sep 27: Complementary slackness conditions. Formulation of 2-layer
graph layout as an integer program. Read: pp
62-68 and for graph layout the paper
of Junger et al.

Sep 29. The revised simplex method. Read text: Ch 7 to p. 105.

*
return
to*: course home page