Lecture Summaries  for 308-566A                     Autumn 2002

      also check:announcements                        return to:course home page

Text
        Linear Programming, V. Chvatal

All classes after Nov 7 are compulsory!
Nov 21, 26, 28, 29(1-2:30) Class Presentations.

Nov 19: Interior point methods part 2. Short and long step methods. Predictor-corrector method.
Nov  14:  Introduction to interior point methods.  Read Handout:  Chapter1 of Primal-Dual Interior Point Methods
      by Steven Wright.
Nov  12:  Polynomial time methods for linear programming. The ellipsoid method.
        Read:  The appendix of Chvatal (The one in his book that is...)
Nov  7: Class Test.
Nov 5: Matrix Games.  We played the game of Mora incorrectly in class.  The payoff is not  made with the
coins that we play with, these are just tokens ( we could just as well play by showing fingers instead).
For the way we played (using  the  tokens  in play as the payoff) the optimum strategy is completely
different (try to find  it!).  Probably that is why I was cleaned out. Read : Text chapter 15.
Oct  31: Integer Programming via Gomory/Chvatal cuts and the dual simplex method.
Oct 29: More on network flows. Tree solution and integrality. Initialization. Avoiding cycling.
                  Read chapter 19 up to page 308.
Oct  24: Introduction to Network Simplex method. Economic interpretation and relation to simplex method.
Oct  22:  Dual  simplex  method,  adding new  constraints to an optimal dictionary.  
                Adding new variables and reoptimization via the  primal revised simplex method.
                 pp148-156. (Revised dual simplex method optional)
Oct  17:  Revised simplex method illustrated. Economic interpretation.
Oct 15:  Introduction to revised simplex method.  Read Chapter  7
Oct  10:  Class test. 
Oct  8:  Economic interpretation of  duality,  complementary  slackness, and the simplex method.

Oct. 1:  Proof of weak and strong duality theorems. Assignment 2 distributed. Solutions will be posted
   October 9. Read the rest of Chapter 5.
Sept.  26:  Proving the answer correct for each outcome: infeasible, unbounded and optimum solution.
   Dual linear program.  Taking care of equations and  unconstrained  variables.  Read:  pp54-57

Sept 24: For Assignment 1, maple is useful for computing the dictionaries. See maplehowto.  
        Some geometrical insight into dictionaries and pivoting. Klee-Minty examples of
        squashed hypercube for worst case examples of the simplex method. Read Chapter 4

Sept. 19: How to solve a system of linear inequalities. Handout is here. Assignment 1 distributed.

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

Sept. 12: How to solve an LP from scratch. Read: Text Chapter 2

Sept. 10: 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 5: Introduction to Operations Research, Mathmetical Programming, Linear Programming and
          Integer Programming. Course outline and requirements. Buy text!