Lecture Summaries for COMP
566
Autumn 2006
also check:announcements
return to:course home page
Text
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