Math 441 Section 201
Mathematical Modeling: Discrete Optimization Problems
|Online Course Material
New Room: MATH 202
Assignment 1 due Tuesday Jan 14, 2014
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. It is a Arts degree `research intensive approved course' which is a degree requirement for a B.A.
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.
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.
The Course Outline gives a timeline for projects. It is important that groups
and projects are chosen early. I will accept project proposals on Thursday Feb 6.
Melissa, Daniel and Shaun are tackling a diet problem. Canada Food Guide will figure prominently.
presentation Thursday Feb 27. First diet had many servings of carrots but ideas how to diversify the diet are being explored.
Yuzhou, Jackie, William might try doing the assessor's job.
presentation Thursday Mar 6. A target area of Shaugnesssy was chosen.
Alfred, Jonathan, Gary are looking at Markowitz Portfolio Model
presentation Tuesday Mar 4 with large datasets examined.
Colin, Alexander, Brian video game team analysis (Pikachu?)
presentation Thursday Mar 6. Simulation running well to determine which of two pokemon characters would win. 10,000 runs can determine useful data for a payoff matrix. Playing a team of 6 still to be tried.
Timon, Tony, Jianwen car sales planning
presentation Thursday Mar 6. A dealers ordering decisions explored by Network Flows (for deterministic slaes) and Dynamic Programming (for probabilistic sales). Some refinements should make this problem quite interesting.
Banghao Harley, Yi Hockey Team selection
presentation Thursday Feb 27. First team selection has been done! The group hopes to submit some teams to the CBC fantasy pool.
Ray, Jie, Xinyuan TA assignment but can 25x60 variables be handled?
presentation Tuesday Mar 4. Interesting data collection ideas. Is program too large?
Chelsea, Carson, Clement Criminal Element (gangster). Initial solution obtained.
presentation Tuesday Mar 4. A larger problem of 45 wards was solved in 2.5 hours!
Jacqueline, Doug, Xiaoyu are exploring the diet problem
presentation Tuesday Mar 4. A quite reasobable diet proposed that tries to balance time with preparation time. At least Doug doesn't like preparation time.
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 Thursday February 27. 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.
We will have about 15 minute group presentations as progress reports on Thursday February 27 and Tuesday March 4. 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. The final project is Due Tuesday April 1.
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
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 also scheduled to teach 15:00-16:00 MWF. I typically do not read my email from home (i.e.
evenings and weekends).
Outline: grading scheme etc.
Assignment 1 due Tuesday Jan 14.
Assignment 2 due Tuesday Jan 21.
Assignment 3 due Thursday Jan 30.
Assignment 4 due Tuesday Feb 11.
the following for 1 a): Swimmeet file
Assignment 5 due Thursday Mar 6.
Slick Oil (vertically integrated oil company). Slick oil file
problem file, LINDO file for
Slick Oil , LINDO file for
Slick Oil with a number of variables as a constant
Hiring Firing problem files
statement, LINDO file,
Absorptivity files LINDO file,
of data , LINGO
An integer Linear Program selecting for chemicals to provide coverage over a range of wavelength.
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
Fano Plane and Projective Planes by Integer Linear Programming LINGO
The Karush-Kuhn-Tucker conditions and one application to the Markowitz Portfolio Model are decribed in KKT file with LINDO
Network Flow template LINGO
PERT network template (Chemical Laboratory Remodelling) LINGO file
Dynamic programming notes for basic formulation without or with discounting.
spreadsheets for the two cases. Sheet 1 has the basic formulation. Sheet 2 has the discounting version.
Construction Speedup Problem how to spend $70,000 effectively. Construction Speedup Spreadsheet
spreadsheets for stochastic dynamic programming.
Various Reference files. Some are some nice and short descriptions from the AMS but also other information as well. If you suggest a link, I'll add it.
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!
version of the travelling salesman problem for the New York Subway
website on unusual TSP algorithm, a bit too small to be useful.