Lecture Summaries  for COMP 566                     Autumn 2006

      also check:announcements                        return to:course home page

        Linear Programming, V. Chvatal

Sep 5  What is operations research, mathematical programming and linear programming. The diet problem and its solution. Criticisms of the optimum solution, and some remedies.
Read: text Chapter 1.

Sep 7  Formulating a linear program in standard form. Dictionaries, bases, co-bases, slack variables and pivoting. How to solve a small feasible LP from scratch.  Read: text Chapter 2.

Sep 12  The simplex method for LPs for which the initial dictionary is feasible. Termination at optimality or with an unbounded solution. A proof of optimality from the final dictionary. Cycling example. Read: Chapter 3, pp 27-34

Sep 14  Initialization. The two phase simplex method. Fundamental theorem of linear programming. Sign patterns for optimum and unbounded dictionaries. Why for a given problem, dictionaries with both of these patterns cannot exist. Read text Chapter 3, 39-42. Assignment 1 posted.

Sep 19: How fast is the simplex method? The examples of Klee and Minty. Geometry, and geometrical interpretation of the simplex method. Read: Ch: 4 and pp 250-257.

Sep 21: Linear programming duality and the weak duality theorem. Read: Start reading chapter 5. Try to write down the duals for the problems you considered in assignment 1, and figure out what they may mean!

Sept 26: 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  19:  First class test.

Nov 23:  Second class test.

Nov 28,30,Dec 5    Class presentations. Attendance compulsory!

                 return to: course home page