Online Course Material
NEWS
Happy New Year. This course should be a lot of fun for students. It can be
considered a capstone course, giving students an opportunity to use their
mathematical maturity to work on `real world' problems. The course has a
reasonable amount of work and certainly the project takes a lot of time but
students typically enjoy the experience. Also there is no final exam!
This course uses discrete optimization techniques such as Linear programming
and Integer Programming. We will be using software (LINDO, LINGO) for
assignments and possibly the project. The course is organized with 50% for
assignments and 50% for a project. The project is done in a groups of at most 3
and a polished write up is expected. There is no final exam. Contact me if you
have questions before selecting this course.
Computer Lab access. There is a computer lab in LSK 121 whose doors are open
from 7:30am to 6:00pm. If you are inside at closing time you can remain but
there is a time when the alram system is turned on and so you must be out by
7:00pm? Check signs. These late times might be relevant while you are working
on your project. Additional access is available in LSK 310 using PC's. These ar
efaster machines.
Printing is limited to 35 pages so I expect you will be transferring files to
your home computer. Additional pages can be purchased from the Statistics
office (during their office hours!) for $20 for 100 pages. Of course you may
prefer to use a webmail account and transfer your files to a different account
with access to a cheaper printer. Undergraduate Computer accounts are assigned
and I will email with the account name and password. Please email me if you
have difficulty.
The Course Outline gives a timeline for projects. It is important that groups
and projects are chosen early. I will accept project proposals on Friday Feb 4.
Some changes are possible but I wish the groups to begin exploring their
project early. In particular, I would like a written report and verbal report
on or before Friday February 25. It is a chance for you to see how your group
should be organized to produce a report and a chance to contemplate the scope
of your project and the difficulties you might encounter. Consultation with me
is essential. I can help you identify the questions that you might focus on and
indicate parts of the project that are likely to be hopeless. It is your
responsibility to make the project interesting for me. There is no `right'
answer. You might find useful information in the handout Project Information.
Groups formed:
Andrew, Mikhael, Shannon (a bus problem; sample problems run) report Monday Feb 28 gave a formulation and revealed some of the computational challenges. Larger scale problems have been solved.
Katii, Shanshan, Wenqian (Markowitz Portfolio problem) report Wednesday Mar 2
Raymond, David, Jan (rug cutting; a solution with 1% waste) report Monday Feb 28 revealed that the initial set of orders can be cut with a miniscule .1% waste. A carefully formulated integer linear programming problem helped.
Amanda, Leah (a diet problem) report Friday Mar 4 with an unexpectedly good diet from McDonalds. But is there enough choice?
Brad, Alistair (gangster problem) report Wednesday Mar 2. Some preliminary solutions for 35 with remarkably good 60-40 splits.
We will have 15 minute group presentations as progress reports on Monday Feb 28 and Wednesday March 2. Aim to have a nice overview of the problem (this will probably be useful later on when you are doing your write up) and give some sample input/output to indicate your progress to date.
Grading this course can be a challenge. It is disconcerting for students that
they won't get 100% for the correct answer. We give the top marks only to those
with clear and interesting writeups. The average in the course will probably be
in the low 70's. The overall grading distribution will be reminiscent of an
Arts course. I expect many good results but only the occasional stellar
writeup.
Some LINDO data files LINDO files
The notes look authoritative when typed so be wary. They may look perfect but
may still contain errors! I don't have an editor.
I arrive most days by 9:00. I typically do not read my email from home (i.e.
evenings and weekends).
Course
Outline: grading scheme etc.
Assignment 1
due Monday Jan 10. You should have a paper copy of the this and the associated
file.
Assignment 1
solutions
Assignment 2
Vista Properties handout/information
Assignment due Wednesday Jan 19..
Assignment 2
solutions
Assignment 3
Assignment due Monday Jan 31. I think the assignment is longer than Assignment
2. Ask questions. I will be available after class until 5 on Wednesday to
discuss your initial model. Have you gotten the 21.03 yet?
Assignment 3
solutions
Assignment 4
due Monday Feb 7. This is another integer linear programming assignment. Use
the following for a): Swimmeet file
Assignment 4
solutions
Assignment 5
Assignment 5 due Wednesday Feb 23.
Assignment 5
solutions
Assignment 6
Assignment 6 due Wednesday Mar 16. Spreadsheet for question 3
Assignment 6
solutions
Spreadsheet solution
Assignment 7
Assignment 7 due Monday April 4.
Slick Oil (vertically integrated oil company). Slick oil file
problem file, LINDO file for
Slick oil
Hiring Firing problem files
Problem
statement, LINDO file,
or LINGO
file
Absorptivity files LINDO file,
or speadsheet
of data , LINGO
file,
Branch and bound example showing how to use
this to solve an integer (or mixed integer) programming problem.
Piecewise Linear Curves The SOS2
formulation (specially ordered sets of size 2)
Jobshop Files Machine
Shop job scheduling problem. , LINDO file
, LINGO
file
Fano Plane and Projective Planes by Integer Linear Programming LINGO
file
Network Flow template LINGO
file
PERT network template (Chemical Laboratory Remodelling) LINGO file
Dynamic programming notes for basic formulation without or with discounting.
Also
spreadsheets for the two cases. Sheet 1 has the basic formulation. Sheet 2 has the discounting version.
Cosntruction Speedup Problem how to spend $70,000 effectively. Cosntruction Speedup Spreadsheet
spreadsheets for stochastic dynamic programming.
Various Reference files.
Linear
Programming Theorems
Brief
discussion of Travelling Salesman problem
Brief
A version of the travelling salesman problem for the New York Subway
Studying Sudokus
Bin Packing
|