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!