Optimization IB

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.

Course notes

• 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.

Examples sheets

• exsheet.pdf

Overheads

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

Topics I have covered are:

1. set partitioning
2. job scheduling
3. optimal electricity generation and distribution
4. insects as optimizers
5. project assignment in CUED
6. examples of very large LPs
7. how large an LP can we solve?
8. on-line bin packing
9. airline luggage
10. MacDiet problem
11. hanging chain
12. hanging springs puzzle
13. string covering (an open problem)
14. Braess's paradox
15. more examples of very large LPs
16. rendezvous problem

• oheads.ps, oheads.ps.gz 

Exam questions

This file has exam questions from 1985-1997.

• tripos.ps

Recommended books

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

Related courses

Other items of interest

• 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.