### Lecture Summaries for COMP
566
Autumn 2008

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

**Text**

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