University of Cambridge > Mathematics > Statistical Laboratory > Richard Weber > Mathematics of Operational Research

Mathematics of Operational Research

This is a home page for a course of 24 lectures to Cambridge MMath/MASt (Part III) students. It was last given in the autumn of 2010 by me. It will next be given in winter 2012 by Dr Felix Fischer, who will be making some changes to the topics that are covered.

This material is provided for students, supervisors (and others) to freely use in connection with this course. Copyright remains with the author.

This course covers a selection of mathematical tools and models for operational research, in particular, linear programming, algorithms, and game theory. It does not cover statistical and stochastic methods, such as queueing theory, or stochastic dynamic programming, which are also important mathematical tools in OR. The coverage of each topic (such as linear programming) is taken to a level beyond that which is commonly found in any undergratuate course, but stops short of what might be covered in a course that is wholely devoted to that topic.

Contents

  1. Lagrangian Methods
  2. Linear Programming
  3. The Simplex Algorithm
  4. Advanced Simplex Procedures
  5. Complexity of Algorithms
  6. Computational Complexity of LP
  7. Ellipsoid Method
  8. The Network Simplex Algorithm
  9. Transportation and Assignment Problems
  10. Maximum Flow and Shortest Path Problems
  11. Algorithms for Shortest Path Problems
  12. Semidefinite Programming
  13. Branch and Bound
  14. Travelling Salesman Problem
  15. Heuristic Algorithms
  16. Two-person Zero-sum Games
  17. Solution of Two-person Games
  18. Construction of a Nash Equilibrium
  19. Cooperative Games
  20. Coalitional Games
  21. Shapley Value and Market Games
  22. Auctions
  23. Auction Design
  24. Games and Mechanism Design
Please send me email with comments or corrections on my lectures, the notes or the examples sheet. I am very glad to receive comments and suggestions from students studyng the course.

Lecture Notes

These are notes for the 2010 course. 

2010 Lectures 1-24 in side-by-side A5 format

2010 Lectures 1-24 in full size A4 format

They are mostly complete, but I may make changes at the course progresses. 

Since the course began this year I have made some changes to the notes  as follows:

Compared to previous years, some topics have be deleted and others added. So not all past exam questions remain relevant. In particular, I have
REMOVED: Rigorous details for the Ellipsoid Algorithm, some trivial material about representation of some integer programs, Facility Location Problem, Joint Maximization of Profits, Evolutionary Games and analysis of some Stackelberg leadership games.
ADDED: Semi-definite Programming, Primal-Dual Interior Point Algorithm, Lemke-Howsen Algorithm, Linear Complementarity Problem, and all material in Lecture 24.

Supporting materials

A file of overheads, some of which I have used in lectures.

For Rendezvous Problem (Lecture 12) see seminar Symmetric Rendezvous Search.

Those interested in Semidefinite Programming can read more in Semidefinite Programming, by Vandenberghe and Boyd. A good program for solving semidefinite programs (and linear programs) using an interior point method is SeDuMi. This is what I used for my numerical research on the Rendezvous Problem.

Seminar slides on Disputed Garment Problem and Bargaining (used in Lectures 19-21: Cooperative and Coalitional Games)

Section 24.2 is taken from Games and Price Mechanisms for Distributed Control, by Anders Ratzner

Further material related to Section 24.3 can be found in my seminar slides
Incentivizing Participation in Resource-sharing Networks (2007)
I discussed in Lecture 24 pages 29-41 of the above talk - which contain similar content to section 24.3 of the notes.
See also, Economic Issues in Shared Infrastructures (2009)

Examples classes

There will be 3 examples classes for this course. These will be in Room 4 at 4pm on Wednesdays Nov 10, Dec 1 and Jan 19.

Examples sheets

Examples sheet 1

Examples sheet 2

Examples sheet 3

Past Exam Papers

Links to exam papers since 2001 are: 20112010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001.
Here also is a single file of all these examination papers (1.4Gb)

Recommended Books

The principle reference for the course is the set of notes that I have written and which have been the basis for the lectures.

L.C. Thomas, Games, Theory and Application, Wiley, Chichester (1984).
  1. M.S. Bazaran, J.J. Harvis and H.D. Shara'i, Linear Programming and Network Flows, Wiley (1988).
  2. Bertsimas and J.N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific (1997).
Wikipedia entries for George Danzig and John Nash.

Simple2 A LP solver. Simple2x is a small program written to run under Windows and designed to assist students to learn the simplex algorithm. It takes the hard labour out of performing pivot operations and it may be configured to prompt the choice of pivot elements.

Archive

These are notes for the 2007-09 course:

2007-09 Lectures 1-24 in side-by-side A5 format  

Notice to external persons accessing this page

University of Cambridge > Mathematics > Statistical Laboratory > Richard Weber > Mathematics of Operational Research

Last modified: 02 December 2010