Lecture Summaries  for 308-566A                     Autumn 2001

      also check:announcements                        return to:course home page

        Linear Programming, V. Chvatal

November 6: Second class test, covers all material below except October 18 and 30.

November 1: Cutting planes for integer programming. Read: handout, section 14.1

October 30: Guest lecture by Bohdan Kaluzny: case study and cplex.

October 25:  Inventory control problem via networks. Unimodular matrices. Read: pp. 320-328.

October 23: Network Simplex method, duality and complementary slackness. Read: 291-307

October 18: Integer programming, relationship to P/NP question.

October 16: Dual simplex method and sensitivity analysis. Read pp 148-162.

October 11: General LP problems: how to handle bounded variables. Read: pp118-129.

October 9: Revised simplex method. Eta matrices and fast update of basis matrix. Read: pp 97-111.

October 4: First class test. Closed book - calculators allowed. Covers all material below.

October 2: Finiteness of Bland's rule. Classification of dictionaries. Generalized duality. Read: pp37-8, 137-141.

September 27: Strong duality and proof of duality theorem. Complementary slackness. Read: 57-68.

Sept. 25: Getting upper bounds. Duality and weak duality theorem.  Read: pp 54-57.

Sept. 20: Complexity of the simplex method. Read: Chapter 4.

Sept. 18: More on solving Simplex method. Pivot selection rules. Unbounded and infeasible problems.Cycling in the simplex method. Initialization. Bland's least subscript rule to avoid cycling.
Read Chapter 3 except pp 34-8. Assignment 1 distributed.

Sept. 13: Saxby foods example of production scheduling. How to solve an LP from scratch. Read: Text Chapter 2

Sept. 11: Polly's diet problem. Formulation, solution by Maple and discussion of solution. All solutions costing at most a dollar are here.
           Read: Text Chapter 1

Sept 6: Introduction to Operations Research, Mathmetical Programming, Linear Programming and Integer Programming. Course outline and requirements. Buy text!