Course outline.

Grades, software, notes, and other material will be posted on LMS.

Piazza: the piazza page for the class is here. This term we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to me, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com.

Office hours:

Scores will be available on LMS

Projects: Presentations will take place in Troy 2012 on Wednesday May 1, from 3-6pm. Please make sure your device has a way to connect to the HDMI projector.

Midterm Exam: In class on Friday, March 15.
It will cover everything seen in class through Friday, March 8 (Lecture 15).
You can bring one sheet of handwritten notes, no larger than 8.5" x 11". You can write on both sides.

Old exams: Solutions from 2014 and earlier are only available if you are logged into the RPI VPN.

• The midterm exam from 2022. Here are the solutions. Mean: 61%, median 65%, StDev 20.3.
• The midterm exam from 2020. Here are the solutions. Here are the robust ampl model and run file for genenerating the instance in question 3, where you can just change the seed. Here are the robust ampl model and run file, which require the use of a data file containing the matrix A. Mean: 81%. Median: 82%. StDev: 11.3.
• The midterm exam from 2018. Here are the solutions. Mean: 75%. Median: 75%. StDev: 15.7.
• The midterm exam from 2016. Here are the solutions. The mean was 74%.
• The midterm exam from 2014. Here are the solutions. The mean was 69%.
• The midterm exam from 2012. Here are the solutions. The mean was 66%.
• 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. Solutions are available on LMS.
• Homework 2. Solutions are available on LMS.
• Homework 3. Solutions are available on LMS.
• Homework 4. Solutions are available on LMS.
• Homework 5. Solutions are available on LMS.
• Homework 6.

Information about AMPL. The software and instructions will be available on LMS.

Notes: These are typed pdf notes. Most of them are only available if you are logged into the RPI VPN (this includes all files on the server eaton.math).

• Introduction, basic feasible solutions, duality, and the simplex algorithm.
  • Lecture 1: Introduction.
    • Some examples: handout, slides, ipad.
    • Standard form: handout, slides, ipad.
    • Linear algebra background: handout, slides, ipad.
    • Affine sets: handout, slides, ipad.
    • Faces: handout, slides, ipad. on webex.
    • Link to the recorded lecture
  • Lecture 2: Basic feasible solutions, degeneracy: handout, slides, ipad. Link to the recorded lecture
  • Lecture 3: Duality.
    • Motivation: handout, slides, ipad.
    • Constructing a dual problem:: handout, slides, ipad.
    • Duality theorems: handout, slides, ipad.
    • The Farkas Lemma: handout, slides, ipad.
    • Link to the recorded lecture
  • Lecture 4: The simplex algorithm.
    • An example: handout, slides, ipad.
    • An iteration: handout, slides, ipad.
    • Strong duality: handout, slides, ipad.
    • The simplex algorithm: handout, ipad.
    • More discussion of simplex: handout, slides, ipad.
    • Link to the recorded lecture
  • Lecture 5:
    • Handling upper bounds: handout, slides, ipad.
    • Multiple optimal solutions and degeneracy: handout, slides, ipad.
• Revised simplex, resolution.
  • Lecture 6:
    • Revised simplex method: handout, slides, ipad.
    • More on revised simplex: handout, slides, ipad.
    • Introduction to AMPL: handout, slides, some examples.
  • Lecture 7:
    • Dual simplex method: handout, slides, ipad.
    • The Klee-Minty cube: handout, slides, ipad.
    • Fourier-Motzkin elimination: handout, slides, ipad.
    • Using Farkas to prove strong duality: handout, slides, ipad.
    • Resolution: handout, slides, ipad.
  • Lecture 8: The Weyl and Minkowski theorems: handout, slides, ipad.
• Column generation methods.
  • Lecture 9:
    • The ellipsoid algorithm: handout, slides, ipad.
      Here is the New York Times page on the discovery of the ellipsoid algorithm from November 27, 1979.
    • Introduction to Dantzig-Wolfe decomposition: handout, slides, ipad.
    • An example of Dantzig-Wolfe decomposition: handout, slides, ipad.
  • Lecture 10:
    • Exploiting block angular structure with Dantzig-Wolfe decomposition: handout, slides, ipad.
    • Lagrangian relaxation: handout, slides, ipad.
    • A cutting plane method for solving a Lagrangian relaxation: handout, slides, ipad. (Delayed until Lecture 12.)
    • See also a computational study of Dantzig-Wolfe decomposition from 2001.
  • Lecture 11:
    • The cutting stock problem: handout, slides, ipad.
    • Crew scheduling: handout, slides, ipad.
• Problems on graphs and networks.
  • Lecture 12:
    • Graph theory: handout, slides, ipad.
    • LP formulations of network flow problems: handout, slides, ipad.
  • Lecture 13:
    • Network simplex: handout, slides, ipad.
    • Multicommodity network flows: handout, slides, ipad.
  • Lecture 14:
    • A network interdiction problem: handout, slides, ipad.
• Stochastic programming.
  • Lecture 14:
    • Introductory material: handout, slides, ipad.
    • The newsvendor problem: handout, slides, ipad.
  • Lecture 15:
    • The L-shaped decomposition method: handout, slides, ipad.
    • An example of the L-shaped decomposition method: handout, slides, ipad.
  • Lecture 17:
    • Sample average approximation: handout, slides, ipad, mp4 audio with screen capture.
    • Risk measures: handout, slides, ipad.
    • Links to the webex files from 2020.
    • Some AMPL files for stochastic programming for a capacity expansion problem:
      • model file, data file for 10 scenarios, data file for random number of scenarios, run file for random number of scenarios.
      • CVaR: model file, use with both a data file from above and a data file with the CVaR parameters.
      • L-shaped: model file, run file for random number of scenarios (uses the data file for random number of scenarios from above).
      • Robust: model file, data file to find the robust solution of an LP; here is the output.
  • Lecture 18:
    • Robust optimization: handout, slides,
  • The results on sample average approximation can be found in a tutorial on stochastic programming by Shapiro and Philpott.
• Interior point methods.
  • Lecture 18:
    • Strict complementarity: handout, slides, ipad.
    • Links to the webex files from 2020.
  • Lecture 19: The primal affine method:
    • handout for part 1, handout for part 2, slides, ipad.
    • Links to the webex files from 2020.
    • See also Sections 9.1 and 9.2 in the Bertsimas and Tsitsiklis text.
  • Lecture 20:
    • The central path: handout, slides, ipad.
    • Links to the webex files from 2020.
    • See also Chapter 2 of the Wright text.
    • Primal-dual interior point methods: handout (part 1), handout (part 2), slides, ipad.
    • Complexity: handout, slides, ipad.
    • Links to the webex files from 2020.
    • See also Chapters 1 and 3 of the Wright text.
    • See also Section 9.5 in the Bertsimas and Tsitsiklis text.
  • Lecture 21:
    • Short step path following methods: handout, slides, ipad.
    • Predictor-corrector methods, part 1: handout, slides, ipad.
    • Predictor-corrector methods, part 2: handout, slides, ipad.
    • Links to the webex files from 2020.
    • See also Chapters 5 and 10 of the Wright text.
  • Lecture 22:
    • Limit points handout, slides, ipad.
    • Homogeneous self-dual formulation: handout, slides, ipad.
    • Interior point cutting plane methods: handout (part 1), handout (part 2), slides, ipad. This material is based on a paper.
    • Links to the webex files from 2020.
    • See also Chapters 5 and 9 of the Wright text.
• SDP and SOCP.
  • Lecture 23:
    • An SDP relaxation of MaxCut: handout, slides, ipad.
    • Duals of semidefinite programs: handout, slides, ipad.
    • Links to the webex files from 2020.
    • See also pages 168-171 of the Wright text.
  • Lecture 24:
    • Examples of duals of semidefinite programs: handout, slides, ipad.
    • Barrier methods for SDP: handout, slides, ipad.
    • Links to the webex files from 2020.
    • See also pages 168-171 of the Wright text.
  • Lecture 25:
    • Simultaneous diagonalization: handout, slides, ipad.
    • Links to the webex files from 2020.
    • More on SDP: handout, slides, ipad.
    • Links to the webex files from 2020.
  • Lecture 26:
    • Second order cone programs: handout, slides, ipad.
    • More on robust programming: handout, slides, ipad.
    • Links to the webex files from 2020.
  • Lecture 27:
    • Conic optimization: handout, slides, ipad.
    • Completely positive programming: handout, slides, ipad.
    • Sensor location and rank minimization: handout, slides, ipad.
    • Links to the webex files from 2020.

Handouts:

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

Papers and resources:

• An electronic copy of the textbook for the second half of the course is available for free through the library: S. Wright, Primal-dual Interior Point Methods, SIAM, 1997. Note: more generally, SIAM e-books are free to RPI students through the library. In addition, SIAM membership is free for RPI students, and SIAM books are discounted 30% for members if you buy directly from SIAM.
• The book A First Course in Linear Optimization, Third Edition, Reex Press, 2013-17 by Jon Lee is available online.
• 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.
• Issue 87 of the Mathematical Optimization Society newsletter Optima, discussing the geometry of polyhedra and simplex pivoting rules.