Math 373: Mathematical Programming and Optimization I, Spring Term, 2008.

Relevant course material will be made available on this webpage as the course progresses.

  • Course Outline, MSWord format

  • List of known errors and typos for the course notes. Please let me know of whatever other errors and typos you find and I will update the list.

  • Assignment 1 will be due on Tuesday, May 13th.

  • Last year's midterm exam (PDF file)

  • Assignment 2 will be due on Tuesday, May 20th.

  • The errata file is now accessible :-)

  • Assignment 3 will be due on Tuesday, May 27th.

  • Assignment 4 will be due on Tuesday, June 3rd.

  • Assignment 5 will be due on Tuesday, June 10th.

  • Last year's final exam (PDF file)

    Topics covered:

  • Week 1: Intro to optimization, plotting feasible region and level curves, solving 2-variable LPs, LP problem formulation including min-cost network flow and integer programs such as bipartite matching/job placement assignment, packing problem (minimizing a max{ } function), the Simplex Method (optimality conditions, checking for unboundedness.)

  • Week 2: Feasibility and the Two-Phase Simplex Method, The fundamental theorem of linear programming, dual bounds on objectives, dual problems in standard form, duality theorem, complementary slackness, "shadow prices" or marginal costs.

  • Week 3: Revised Simplex Method, midterm review, assignment 1 back, assignment 2 back, midterm exam, midterm back (65% average) and take-up, revised simplex example.

  • Week 4: Two-Phase example of revised simplex method, convexity, geometry of the simplex method, general duality, Farkas' Lemma and the Theorem on Inconsistent Systems.

  • Week 5: Assignment 3 back, Theorem on Inconsistent Systems examples, the Consequence Theorem, Intro to Sensitivity Analysis, Assignment 4 due, Integer Linear Programs, generating Gomory Cuts, the Cutting Plane Method for ILPs, the geometry of cutting planes, transportation problems and their dual problem, initial basic feasible solutions to transportation problems.

  • Week 6: Assignment 4 back, Transportation simplex method, Assignment 5 due, final exam review, final exam.