Homework scores to date, for people who've handed in all six homeworks. Updated May 5th.

Project:
The presentation and report details are available.
An update is required on April 14.

Solutions to the midterm exam.
The Midterm Exam took place in class on Thursday, April 3. You could bring one 8.5x11 sheet of handwritten notes (you could write on both sides). The exam covered everything seen in class through March 31.
Old exams: (pdf files)

• The midterm exam from 2006. Mean: 69%. Here are the solutions.
• The take home midterm exam from 2004. Here are the solutions.
• The take home midterm exam from 2002. Here are the solutions.
• The take home midterm exam from 2000. Here are the solutions.

Homework:

• Homework 1 (pdf file). Here are the solutions.
• Homework 2 (pdf file). Here are the solutions.
• Homework 3 (pdf file). Here are the solutions.
• Homework 4 (pdf file). Here are the solutions.
• Homework 5 (pdf file). Here are the solutions.
• Homework 6. Revised on April 17.

Information about AMPL.

Notes: Handwritten scanned copies of my notes from previous semesters (pdf files):

• Introduction, basic feasible solutions, duality, and the simplex algorithm.
• Revised simplex, resolution (including the Weyl and Minkowski theorems and Fourier-Motzkin elimination).
• The ellipsoid method.
• Probabilistic analysis of the simplex method.
• Game theory.
• Dantzig-Wolfe decomposition, cutting stock problems, network simplex, multicommodity network flows.
• Stochastic programming.
• Introduction to interior point methods: strict complementarity, the central path, primal-dual framework, complexity theory, affine methods, the centering direction, a potential-reduction method.
  Pages 1-9 covered on March 17.
  Pages 10-22 covered on March 20.
  Pages 24-27, 29, and 32-35 covered on March 27.
  Pages 36-40 covered on March 31.
• Barrier methods.
  Pages 6-18 covered on March 24.
• Long-steps, quadratic convergence, predictor-corrector, finite termination, crossover, infeasible methods.
  Pages 11-16 covered on April 7.
  Pages 6-10 covered on April 10.
• Homogenized methods, Mehrotra's predictor-corrector, sparse linear algebra.
  Pages 5-9, 19-25 covered on April 10.
• SDP and SOCP.
  Pages 1-12 covered on April 14.
  Pages 17-20, 24, 27, 30, and 33 covered on April 17.
  Pages 13-16, 21-23, and 25-26 covered on April 24.
• Interior point cutting plane methods and linear programs with complementarity constraints.
  Slides 28-52 covered on April 28. (These are pages 37-64 in the pdf file.)

Handouts:

• An example of Dantzig-Wolfe decomposition.
• The dual simplex algorithm.
• Handling upper bounds in the simplex algorithm
• An iteration of the simplex algorithm and the algorithm.
• Dimension, polyhedra, and faces.
• Subspaces, affine sets, convex sets, and cones.
• Linear algebra.

Papers and resources:

• Introduction to Stochastic Programming by Birge and Louveaux is available online via the RPI library.
• The stochastic programming text by Kall and Wallace is available online.
• A computational study of Dantzig-Wolfe decomposition, the doctoral thesis of James Tebboth.
• A paper on a column generation approach to a clustering problem.
• Here is some further reading about the Weyl-Minkowski theorems showing that constrained polyhedra are generated polyhedra and vice versa. This material is taken from the book Theory of Linear and Integer Programming, by Alexander Schrijver. This is an excellent text for the more theoretical aspects of linear programming, and it is available in paperback: check bestbookbuys.com or evenbetter.com.
• Solving real world linear programs, a survey paper by Bob Bixby, the author of the original simplex code in CPLEX.
• Myths and counterexamples in linear programming (and other areas of optimization). This site shows that you have to be careful about your assumptions when you state some things that are "obvious" in linear programming.