**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!

*return to*: course home page