University of Cambridge > Mathematics > Statistical
Laboratory > Richard Weber > Optimization
This material is provided for students, supervisors (and others) to freely use
in connection with this course. Copyright remains with the author.
Optimization IB Constraints for problem P
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
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.
How to view and print: There are 56 pages of notes available as a pdf file. The notes are formatted as two
side-by-side pages per A4 sheet.
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.
There is a single examples sheet, available as a pdf file of 6 pages. The topics that the questions cover
appear in the same order as topics are covered in lectures and you will find a recommendation on the sheet
concerning the work you should do for your supervisions. Viewing and printing is identical as for the notes above.
I include a small (non-examinable) digression half way through each lecture.
Topics I have covered are:
These examples and other material are included in this file of overhead projector slides.
- 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
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.
There are two courses in Part II that build on what students learn in this course. In Part IIA there is
Algorithms and Networks. In Part IIB there is Optimization and Control.
Other items of interest
Notice to external persons accessing this page Please click here.University of Cambridge > Mathematics >
Statistical Laboratory > Richard Weber
- 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.
Last modified: 17 Janaury 2007