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

This is home page for a course of 12 lectures to first and second year Cambridge mathematics students.

**There is a more modern version of this course here.**

Each lecture is as self-contained as possible and has course notes amounting to four or five A4 pages. Click here for the table of contents.

I have also made additional notes about things I said in lectures and questions students have asked.

There is a single examples sheet and a file of exam questions. Students should receive two supervisions on the examples sheet. There are two recommended books. If you enjoy this course then you should consider related courses in Part II and other items of interest.

- O.pdf (119K) has all the above in a single file

Where to collect photocopies of the notes: You can find copies of notes by using this map to locate the Statistical Laboratory pigeonholes.

I include a small (non-examinable) digression half way through each lecture.

Topics I have covered are:

- set partitioning
- job scheduling
- optimal electricity generation and distribution
- insects as optimizers
- project assignment in CUED
- examples of very large LPs
- how large an LP can we solve?
- on-line bin packing
- airline luggage
- MacDiet problem
- hanging chain
- hanging springs puzzle
- string covering (an open problem)
- Braess's paradox
- more examples of very large LPs
- rendezvous problem

Here are some additional notes which summarise things I said in lectures and which do not appear in the printed notes. I have also made notes about questions that students asked, either in lectures or by coming up to me afterwards.

Here is single fille of all Tripos questions on Optimization for the years 2004-2011

This file has exam questions from 1985-1997.

- Bazaraa, M., Jarvis, J. and Sherali, H., Linear Programming and Network Flows. second edition, 1990, Wiley.
- Luenberger, D., Introduction to Linear and Non-Linear Programmings, second edition, 1984, Addison-Wesley.

- A Pascal program implementing the simplex algorithm.
- An executable program lp_solve that you can easily run on a PC under DOS to compute the solution to linear
programming problems and integer linear programming problems. Click here for an
explanation of how to use the program and instructions on downloading it to your computer.
Spreadsheet programs like Microsoft Excel and Quattro Pro also contain LP solvers that are good for up to about 200 variables.

- An interactive diet solver that will
find your "optimal" diet based on a list of foods you tell it you are willing to eat.
The goal of the diet problem is to find the cheapest combination of foods that will satisfy all the daily nutritional requirements of a person. The problem is formulated as a linear program where the objective is to minimize cost and meet constraints which require that nutritional needs be satisfied. We include constraints that regulate the number of calories and amounts of vitamins, minerals, fats, sodium and cholesterol in the diet. The mathematical formulation is simple, but you will find out by running the model that people do not actually choose their menus by solving this model. The diet problem is one of the first optimization problems to be studied back in the 1930's and 40's. It was first motivated by the Army's desire to meet the nutritional requirements of the field GI's while minimizing the cost. Read more about the amusing history of the diet problem.

- NEOS Guide to Optimization including an overview of optimization, case studies, test problems, and much, much more. Well worth looking at!
- If you are interested in learning about modern interior point methods for solving LP problems, read here.
- Here are some biographical notes about George Dantzig, the originator of the simplex method, on the occasion of his 80th birthday.

- Here are some pointers to files of frequently asked questions on the internet about Linear Programming and Non-linear Programming.
- miscellaneous things in OR/probability/statistics that I find amusing.

Last modified: 17 Janaury 2007