Math Models of OR, Fall 2010.

MATP4700/DSES4770

Contents of this page:

Course Basics

• Course outline, including office hours.
• Scores, including the third exam and the project. The project scores are given as a range, in the interests of preserving some confidentiality. If you missed an exam then your scores are not included. The scores are ordered by decreasing overall score. The final grades were curved, grade modifiers were used, and grades should now be available from SIS. You can pick up your exams and projects from me. Have a good break!
• The book by Rardin is on reserve. This book contains some information on interior point methods.

Homeworks

• Homework 1.
• Homework 2.
• Homework 3.
• Homework 4.
• Homework 5.
• Homework 6.
• Homework 7.
• Homework 8.

Exams

• Information about Exam 1.
• Information about Exam 2.
• Exam 3 will be in class on Friday December 10. It will include one question from Homework 6 or Homework 7 or Homework 8. You can bring one handwritten 8.5"x11" sheet of notes. Some old exams:
  • Fall 2008, along with its solution. The mean on this exam was 72%.
  • Fall 2005, along with its solution. The mean on this exam was 72%.
  • Fall 2004, along with its solution. The mean on this exam was 74%.
  • Fall 2003, along with its solution. The mean on this exam was 72%.
  • Fall 2002. The mean on this exam was 83%. Here is its solution.
  • Fall 2000. The mean on this exam was 68%. The solutions to this exam are no longer available.

Project

• The first part of the project is due on October 5th 8th. The data file is here.
• Here is more information about AMPL and CPLEX.
• The second part of the project is due on November 12th.
• The third part of the project is due on December 10th.

Notes

• Introductory examples. Improving search.
  • Lecture 1, August 31: pages 1-8.
  • Lecture 2, September 3: pages 9-15.
  • Lecture 4, September 10: pages 23-26, 28, 29.
• The simplex algorithm.
  • Lecture 2, September 3: pages 1-9.
  • Lecture 3, September 7: pages 12 and 15-24.
  • Lecture 4, September 10: pages 11, 13, and 14.
• More on the simplex algorithm.
  • Lecture 5, September 14: pages 1-10.
  • Lecture 6, September 17: pages 11-20. Also discuss the the Klee-Minty cube.
  • Lecture 7, September 21: pages 21-29.
• Duality. Dual simplex. Sensitivity analysis.
  • Lecture 10, October 1: pages 1-3.
  • Lecture 11, October 5: pages 4-9, 12-13.
  • Lecture 12, October 8: pages 14-21.
  • Lecture 13, October 15: pages 23-25, 10-11, 26, 27.
  • Lecture 14, October 19: pages 28, 29, 32-34, 37-40, 22. Handout on cutting planes for knapsack problems.
• Network flows.
  • Lecture 15, October 22: pages 1-11.
  • Lecture 16, October 26: pages 12-21.
  • Lecture 17, October 29: pages 22-29.
  • Lecture 18, November 2: pages 30-32.
• Integer programming.
  • Lecture 18, November 2: pages 1-7.
  • Lecture 20, November 9: pages 8, 11, 12, 16, and 17. Here is information on modeling piecewise linear functions.
  • Lecture 21, November 12: pages 9, 10, 13-15.
  • Lecture 22, November 16: pages 18-22. See also the example of solving a knapsack problem.
• Interior point methods. See also the typewritten handouts on the primal affine method and primal-dual methods.
  • Lecture 22, November 16: pages 1 and 9.
  • Lecture 23, November 19: pages 2-8 and 11-12.
  • Lecture 24, November 23: pages 10 and 13-24. See also a handout of a centering example.
• Dynamic programming, part 1 and part 2.
  • Lecture 25, November 30: part 1, pages 1 and 5-16.
  • Lecture 26, December 3: part 1, pages 17-23, and part 2, pages 1-3.
  • Lecture 27, December 7: part 2, pages 4, 5, 8-13.

Homework Solutions:

• Chapter 2.
• Chapter 3, questions 1-15.
• Chapter 3, questions 16-28.
• Chapter 3, questions 29-31, together with Chapter 4.
• Chapter 5, questions 1-10.
• Chapter 5, questions 11-18.
• Chapter 6.
• Chapter 7.
• Chapter 8, questions 1-8.
• Chapter 8, questions 9-11.
• Chapter 8, questions 11-18.
• Chapter 10.
• Homework 7.

Handouts and supplementary material:

• Applications of Optimization
• An interactive formulation of the diet problem is available from the NEOS at Argonne National Lab. The link also includes the ampl code for the diet problem.
• The brewery problem formulated as an AMPL example with sets. Data files can be found in this directory.
• AMPL tutorial, from Gabor Pataki.
• An example of cycling in the simplex algorithm, from Ecker and Kupferschmid.
• Handling upper bounds in simplex.
• A question on complementary slackness. (October 8, 2010.)
• The dual simplex method. (October 8, 2010.)
• Cutting planes for knapsack problems. (October 19, 2010.)
• An example of the network simplex algorithm, from Ecker and Kupferschmid. (October 22, 2010.)
• Modeling piecewise linear functions. (November 9, 2010.)
• The primal affine scaling algorithm. (November 16, 2010.)
• Primal-dual interior point methods. (November 23, 2010.)

Other Resources:

• Information about AMPL.
• Optimization Models for Decision Making, a webbook by Katta Murty that covers similar material to that in this class. The same author also has available a webbook on algorithmic linear algebra.
• Linear Programming FAQ
• Myths and counterexamples in linear programming. This site shows that you have to be careful about your assumptions when you state some things that are "obvious" in linear programming.
• A list of operations research sites.
• RIOT: Baseball Playoff Races. This site uses linear programming to determine when a baseball team is eliminated from contention.