Online Course Material
NEWS
Hope you had a great summer. 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. It also serves a Arts degree `research intensive approved course' which is a degree requirement for a B.A. If you are in a joint degree with another specialty in Arts such as Economics, you may be taking `research intensive approved course' in that other department but you are more than welcome to take this course.
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 does have MATH 340 as a prerequisite. You can discuss with me if this is missing but you are bringing other strengths.
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 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.
The Course Outline gives a timeline for projects. It is important that groups
and projects are chosen early. I will expect project proposals by Wednesday Oct 5. We will have about 15 minute group presentations as progress reports the week of October 28. 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.
Some changes are possible but I wish the groups to begin exploring their
project early.
It is a chance for you to see how your group
should be organized to produce a report. Hopefully you will have some initial computations done and are aware of the difficulties you might encounter. You should contemplate the scope
of your project. 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.
Group Projects for 2015
Rohin, Judah and Brandon will work on the Markowitz Portfolio model. Presented Nov 2. They have a 10x10 covariance matrix to play with.
Yuanyuan, Bassem and Matthias are working together exploring a game Tarneeb (a Middle Eastern game). They will present Nov 4.
Liuke, Jiaqi and Jianfei will work on a cattle farming problem. Presentation Nov 4.
Lei, Hui Shen and Wanqi were going to work on a production problem with a embedded transshipment problem. They are now working on a multi-dimensional bin packing problem.. Presentation Oct 31.
Daniel, Jane (Hua) and Eric (ShiQi) may be exploring optimal exam scheduling. Presentation Oct 31.
Xiaomeng, JiaJun and Daniyar are interested in exploring a diet problem eating at restaurants. McD or Sushi?. They presented Nov 2. McD and Togo were competitive at about $33 per day.
Winson (Guanfeng), Yidan and Ziwei will work on a diet problem; optimal grocery selection. Presented Nov 2. Only about $10 per day.
Chloe, Manni and Natasha are interested in exploring a game that involves cute cats. They will present Nov 4.
Silvia, Beini and Tianwen are interested in cutting rugs. They will present Nov 4.
Sylvester, Naqsh and Billy presented
Oct 31. They considered 3 ways to compute useful splits either by integer linear programming, simulated annealing and genetic algorithms.
The final project is due Friday November 25.
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 am scheduled to teach 10:00-11:00 MWF. I typically do not read my email from home (i.e.
evenings and weekends).
Course
Outline: grading scheme etc.
Assignment 1 question ,
Paper on Property valuation due Monday September 12 Assignment 1 solutions ,
Assignment 2 ,
Vista Properties due Friday September 23 Assignment 2 solutions
Assignment 3 ,
due Wednesday October 5 Assignment 3 solutions
Assignment 4 ,
due Friday October 21 Assignment 4 solutions
Assignment 5 ,
due Friday November 4. Assignment 5 solutions
Assignment 6 and
Spreadsheet
due Friday Nov 18.
Assignment 7
due Friday Dec 2.
Slick Oil (vertically integrated oil company). Slick oil file
problem file,
Slick oil solution file,
LINDO file for
Slick Oil , LINDO file for
Slick Oil with a number of variables as a constant
Hiring and Firing Problem
Hiring Firing input files ,
LINDO file,
or LINGO
file
Absorptivity files LINDO file,
or speadsheet
of data , LINGO
file,
An integer Linear Program selecting for chemicals to provide coverage over a range of wavelength.
Chemical Coverage
Fano Plane and Projective Planes by Integer Linear Programming LINGO
file
Jobshop Files Machine
Shop job scheduling problem. , LINDO file
, LINGO
file
Network Flow template
LINGO
file,
LINDO
file
Pit Mining Problem Cross section ,
Arcs ,Max Flow problem An intermediate flow and augmenting path ,
Max Flow , Min Cut identified as nodes that can be reached by augmenting paths, Optimal Pitmine
Chemical Laboratory Remodelling Project. LINDO input file to determine longest paths using Network Flows. Excel spreadsheet to use Dynamic Programming to compute longest paths.
Labels for network.
Crashing applied to the Chemical Laboratory Remodelling Project. We have increased the durations of three activities: obtain cabinets increased from 10 to 12, finish plumbing and electric increased from 2 to 3 and Install 2/3 Base Cabinets increased from 2 to 3. (The changes resulted in more critical arcs.) New network with more critical arcs
The costs of reducing a (critical) activity by one day become arc upper bounds. Since some activities cannot be reduced in duration (e.g. dummy arcs of duration 0) and so end up with an upper bound of infinity. Crashing Network with the new max flow and the minimum cut identified which becomes the minimum cost way to reduce the duration of the entire project by one day by reducing the completion time of 3 activities (Painter availability, install wall cabinets, install 2/3 base cabinets) each by one day.
Dynamic programming notes for basic formulation without or with discounting.
Also
Excel spreadsheets for the two cases. Sheet 1 has the basic formulation ( printout of spreadsheet ). Sheet 2 has the version with discounting
( printout of spreadsheet ). This spreadsheet has formulas that enable you to change the data and still read off the solution.
Construction speedup example. The solution is not so hard once you have formulated the problem as a dynamic programming problem. In this case, dynamic programming becomes a nice way to order your search of possibilities.
Problem formulation. After the formulation the following spreadsheet solves the problem.
Stochastic Dynamic Programming
example and
spreadsheet We consider optimal ordering decisions to optimize profit in the face of stochastic demand. If we assume that optimal decisions become fixed with time then we have an interesting linear algebra idea that shows that in this case the profit per month is something like $1075.
Graph Theory
Drilling holes at minimum spacing in a metal plate. The minimum number of passes becomes the colouring number of a graph.
Chinese Postman Problem (from Meigu Guan of Shandong Teachers University, Jinan, China) appeals to the minimum weight matching problem.
Euler Theorem ,
Street Map ,
where mail needs to be picked up ,
Just the routes for mail ,
abstracted routes overlayed on map ,
abstracted routes ,
Odd degree vertices noted ,
Odd degree vertices ,
Minimum Perfect Matching on odd degree vertics ,
Graph plus perfect matching .
Plotting Pen Problem (Old Technology) appeals to the minimum weight matching problem. This effort used heuristics to find low weight matchings.
Plotting Problem ,
Tokyo Map ,
Extra motion after Random shuffling of plotting instructions ,
Result of an intelligent person ordering plotting instructions ,
Serpentine Buckets and ordering ,
Matching of extra motion ,
Triangular buckets ordered by Serpinski ordering ,
Matching of extra motion .
Various Reference files. Some are some nice and short descriptions from the AMS (The American Mathematical Society not the Alma Mater Society) but also other information as well. If you suggest a link, I'll add it.
Cookie recipe
Linear
Programming Theorems
Brief
discussion of Travelling Salesman problem
website with an enormous amount of information on the Travelling Salesman problem including the Concorde algorithm in a phone app!
Brief
version of the travelling salesman problem for the New York Subway
Studying Sudokus
Bin Packing
website on unusual TSP algorithm, a bit too small to be useful.
|