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.

Lagrangian Methods
Linear Programming
The Simplex Algorithm
Advanced Simplex Procedures
Complexity of Algorithms
Computational Complexity of LP
Ellipsoid Method
The Network Simplex Algorithm
Transportation and Assignment Problems
Maximum Flow and Shortest Path Problems
Algorithms for Shortest Path Problems
Semidefinite Programming
Branch and Bound
Travelling Salesman Problem
Heuristic Algorithms
Two-person Zero-sum Games
Solution of Two-person Games
Construction of a Nash Equilibrium
Cooperative Games
Coalitional Games
Shapley Value and Market Games
Auctions
Auction Design
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:

Lectures 16-18 (revised 15 Oct 2010).
Lecture 16 (small corrections made in Section 16.4 on 13 Nov 2010)
Lecture 18 (further revised on 17 Nov 2010)
Lecture 18 (corrections to section 18.3 have been made following lecture on 17 Nov 2010)
Lecture 19 revised 17 Nov 2010 (added sketch proof of Nash's bargaining solution)
Lecture 20 corrected a n to 2^n on 4th line of page 82 (Nov 22).
Lectures 22-24 basic outine finalized (Nov 24)
Lecture 23 some improvements were made to pages 92-93 following the lecture, to make some of the ideas a bit clearer.
Lecture 24 some final corrections and improvements were made on 1 Dec.
Some further changes may be made after Lectures 22-24 have been delievered.

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: 2011, 2010, 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).

M.S. Bazaran, J.J. Harvis and H.D. Shara'i, Linear Programming and Network Flows, Wiley (1988).
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.