Course outline.

Office hours: Tuesdays 12noon-2pm, Wednesdays 2-4pm, or by appointment.

Material on reserve in the library.

Scores on the homeworks and the midterm for students who submitted all the homeworks.

Projects: Here is some information about the requirements for your project reports and presentations.

Midterm Exam: The midterm exam will be in class on Friday, April 20. Here is a link to some more information. Here are the solutions. The mean was 66%.
Old exams:

• The midterm exam from 2010. Mean: 71%. Here are the solutions.
• The midterm exam from 2008. Mean: 68%. Here are the solutions.
• 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. Here are the solutions.
• Homework 2. Here are the solutions.
• Homework 3. Here are the solutions.
• Homework 4. Here are the solutions.
• Homework 5. Here are the solutions.
• Homework 6, updated on May 1. Here are the solutions.

Information about AMPL.

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

• Introduction, basic feasible solutions, duality, and the simplex algorithm.
  • Introduction: January 24: Pages 1-8. Pages 5-8 are covered in the first three handouts
  • Basic feasible solutions, degeneracy: January 27: Pages 9-19.
  • Duality: January 31: Pages 20-29.
  • The simplex algorithm: February 3: Pages 30-42. See also two handouts.
  • Multiple optimal solutions, handling free variables and upper bounds: February 7: Pages 43-50. See also a handout.
• Revised simplex, resolution.
  • February 7: Revised simplex method, pages 1-8.
  • February 10: Dual simplex method, via a handout. Fourier-Motzkin elimination, pages 16-22. Resolution, pages 9-15. The Weyl and Minkowski theorems, pages 23-28.
  • February 14: Introduction to AMPL. Using Farkas to prove strong duality, page 29.
• The Klee Minty cube: February 14.
• Probabilistic analysis of the simplex method: February 14. Focus on the results on pages 4, 5, and 9.
• The ellipsoid method: February 17.
• Dantzig-Wolfe decomposition, cutting stock problems, network simplex, multicommodity network flows.
  • February 17: introduction to Dantzig-Wolfe, pages 1-5.
  • February 21: Dantzig-Wolfe iteration and behavior, block angular structure, pages 6-17. Also, an example of Dantzig-Wolfe decomposition.
  • February 24: Lagrangian relaxation, cutting stock problems, pages 18-27.
  • February 28 and March 2: Network simplex, multicommodity network flow problems, pages 28-37.
• Stochastic programming: March 6 and 9. The results on sample average approximation can be found in a tutorial on stochastic programming by Shapiro and Philpott.
• 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, 3-8 covered on March 20.
  Pages 2, 9-22 covered on March 23.
  Pages 24-27 and 29 covered on March 30.
  Pages 32-40 covered on April 3.
• Barrier methods.
  Pages 6-20 covered on March 27.
• Long-steps, quadratic convergence, predictor-corrector, finite termination, crossover, infeasible methods.
  Pages 11-16 covered on April 6.
  Pages 6-10 covered on April 10.
• Homogenized methods, Mehrotra's predictor-corrector, sparse linear algebra, interior point cutting plane methods.
  Pages 1-4 covered on April 6.
  Pages 5-9 covered on April 10.
  Pages 10-14 summarized in ten minutes on April 10.
  Pages 19-25 covered on April 13.
  Slides 3/72 to 30/72 of this talk on interior point cutting plane methods were covered on April 13. The talk is based on a paper.
• SDP and SOCP.
  Pages 1-7 covered on April 13.
  Pages 18-20 covered on April 24.
  Pages 13-15, 17, 27, and 30 covered on April 27.
  Pages 8-12, 22-26, 31-32 covered on May 1.
  Pages 16, 28-29, and 33 covered on May 4. The example on sensor location is here.
  Page 21 covered on May 8.
  May 8: Pages 35/72 to 53/72 and 67/72 to 69/72 from this talk on interior point cutting plane methods should be covered. It is based on a paper.
  The book Convex Optimization, by Boyd and Vandenberghe, contains a wealth of material on SDP, SOCP, and conic programming.
• Completely positive programming. May 8.
• The material on linear programs with complementarity constraints on May 8 is from two talks: slides 4/54 to 14/54 from this one and slides 12/41 to 24/41 from this one.

Handouts:

1. Linear algebra. (Jan 24.)
2. Subspaces, affine sets, convex sets, and cones. (Jan 24.)
3. Dimension, polyhedra, and faces. (Jan 24.)
4. An iteration of the simplex algorithm and the algorithm. (Feb 3.)
5. Handling upper bounds in the simplex algorithm. (Feb 7.)
6. The dual simplex algorithm. (Feb 10.)
7. Extreme points and extreme rays of polyhedra. (Feb 17.)
8. An example of Dantzig-Wolfe decomposition. (February 21.)

Papers and resources:

• The book Convex Optimization, by Boyd and Vandenberghe, contains a wealth of material on SDP, SOCP, and conic programming.
• Introduction to Stochastic Programming by Birge and Louveaux is available online via the RPI library.
• A computational study of Dantzig-Wolfe decomposition, the doctoral thesis of James Tebboth.
• 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.
• Issue 87 of the Mathematical Optimization Society newsletter Optima, discussing the geometry of polyhedra and simplex pivoting rules.