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 3: The bicycle problem (Problem 1.9). Complementary slackness conditions. Read: pp62-68. Assignment 2 posted.

Oct 5: More on complementary slackness, with examples to show how to prove optimality and do sensitivity analysis. Do some exercises on this!

Oct 10: No class (Monday schedule.) Assignment 2 can be handed in Oct 12 in class.
Oct 12: Revised simplex method. Read: pp 97-105.

Oct  17: Conor will be on hand to answer questions and hand back Ass. 2. Send suggestions for topics to him: cmeagh1 at cs.mcgill.ca
Oct 19: Midterm will be held in Burnside Hall 1B23 (basement) 08:35-09:55. It will cover all above material up to and including Oct 12 lecture.

Oct 24: Generalized LP. How to deal with upper and lower bounds implicitly. Read: text pp 118-124.

Oct 26: Network simplex method. Read: pp. 291-303
Oct 31: LP formulation on network model and its dual. Proof of correctness of network simplex method. Application to Caterer's problem. Read: text pp 320-328.

Nov 2: Unimodular matrices. Sufficient condition for total unimodularity. Linear programs with integer solutions. No reading.

Nov 7: Zero sum games. Read: Text Chapter 15
Nov 9: Non zero sum two person games. Read: Notes here
Nov 14,16: Primal-dual interior point methods. Read: class handout

Nov 21: KKT conditions. More on interior point methods.

Nov 23:  Second class test, in Trottier 1080. All material up to and including Nov 9 lecture.

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

                 return to: course home page