MATH 441 Homepage, Fall 2017

This page concerns MATH 441--Math Modeling: Discrete Optimization Problems--Section 101.

This page has the most up-to-date information on the course(s) and supersedes any other document.

News Here is a guide to the grading of presentations, and a presentation schedule.
The final schedule was produced via this optimization procedure.

Final reports should be emailed to me in PDF format by 11:59pm on Tuesday, November 28, and you should give me a hardcopy by our class on Wednesday, November 29; the same Writing Rubric will be used to grade your projects, with "Modeling terminology and content" given a weight of 5, and all other rows each given a weight of 1. The final report should be roughly 3-7 pages (i.e., 600-1400 words); any additional material (data/results/software) should be verifiable (i.e., I should be able to check and duplicate your experiments) and appear either in an appendix to your report and/or as a separate attachment.
Older News The progress report should be roughly 3-5 pages (i.e. 600-1000 words).
Here is sample progress report and its LaTeX source (which I have given a .txt extension).
Here is a Writing Rubric as a guide to the grading of projects. The progress reports will be graded on your overview, motivation, specific questions, and models (which correspond to Sections 1 and 2 of the above sample).
Sample Proposal Talk Here are slides for a sample proposal talk. Proposal talks are optional; each group can have at most one person present the proposal.
Each student needs to give a 5 minute talk--either about the proposal or (later in November) about the research---and be prepared to answer questions on the talk; see grading scheme below.
Markowitz Model We will discuss the Markowitz model and non-linear programming: see
  • this Introduction to the Markowitz Model that I wrote (this is a draft that I'm likely to modify; I will also add some exercises for homework), and
  • my article on Linear Complimentarity and Mathematical (Non-linear) Programming.
    • We will also refer to part of Chapter 24 of "Linear Programming" by Vanderbei, 4th edition.
    Office Hours By appointment for now--email me and let me know when you are free over the next few days. When things get too busy (e.g., near project deadlines) I'll revert to fixed office hours.
    Boards Scans, Etc. Scan of boards for: 09_11, 09_13, 09_15, 09_18, 09_20, 09_22, 09_25, 09_27, 09_29, 10_02, 10_04, 10_06, 10_11, 10_13, 10_16, 10_18, 10_20, 10_23, 10_25, 10_27, 10_30, 11_01, (from this point onward, missing scans indicates no new material and no written class notes)
    11_06 class based on this,
    11_08, 11_10, 11_15, 11_17, 11_24,
    Summaries: First example of an LP (covered Sept 11-15).
    Slides starting week of September 4.
    Gurobi and Maple We will use Gurobi in class examples; we will sometimes also use Maple in class (Maple is available in the labs in LSK 310). I will maintain a separate webpage for examples in Gurobi and Maple.
    Overview This course focuses on a research project that is an application of linear programming (from Math 340); there will also be some new material taught in linear programming, beyond what you have seen in Math 340. For B.A. students, this course counts as a "research intensive approved course." This course will be similar to Prof. Anstee's Math 441 course last year, and will borrow ideas from Prof. van Willigenburg's Math 444 course last year; both these webpages have some good resources.
    Prerequisite The prerequisite for the course is Math 340. We will use the dictionary form of the simplex method, rather than tableau form. If you have not taken Math 340 at UBC, but know the material or bring other strengths to the course, please speak to me.
    Here is my last Math 340 homepage, from Fall 2015. You might look at the exam materials there to know what we covered.
    Textbooks and Sources
  • The textbook "Linear Programming" by Chvatal is recommended; it is the simplest exposition I know, and uses dictionary form.
  • I may refer to parts of "Linear Programming" by Vanderbei, 4th edition, available with your CWL account. This book also uses dictionary form; it is more advanced that Chvatal's textbook.
  • I will refer to my last Math 340 homepage, from Fall 2015 for review and examples.
  • The following textbooks have interesting material on ILPs:
  • I will maintain a webpage listing applications of LP's and ILP's (this may include some MLP's, meaning mixed LP's).
    • Software I recommend that you use Gurobi for projects and homework; it is essentially competitive with best commercial products (such as CPLEX, Mosek), and Gurobi offers convenient, free academic versions. Visit Gurobi's Academic Center to get a license for University Users.
    There is a lab LSK 310 where students will have acces to Maple, MATLAB, and LINDO; hopefully some version of Gurobi will soon be installed there.
    Here is (stand-alone) command line example in Gurobi. I will cover this in class.
    In class I will use Gurobi to illustrate examples; I may at times use Maple to illustrate principles, but you will not need Maple for your homework (or projects).
    You are free to use any optimization software you like for your project and homework; but you need to make sure that your software works. One consideration is how you are going to input data into such software; another consideration is how much speed you need (homework won't involve large data sets).
    Homework Late homework will not be accepted. Your two lowest scores will be dropped in the overall homework computation.
    Homework 1 is due on September 28, 11:59pm at gradescope.com. Homework 1 solutions and PDF of Gurobi files created in the solutions.
    Homework 2 is due on October 19, 11:59pm at gradescope.com. Homework 2 solutions
    Homework 3 is due on November 2, 11:59pm at gradescope.com. Homework 3 solutions and Gurobi files.
    Homework 4 is Exercises~(1)--(3) from (Section 11 of) Introduction to the Markowitz Model, and is due on November 9, 11:59pm at gradescope.com. Homework 4 solutions.
    Homework 5 is due on November 16, 11:59pm at gradescope.com. Homework 5 solutions.
    Homework 6 is due on November 23, 11:59pm at gradescope.com. Homework 6 solutions.
    Writing I recommend using overleaf.com for writing your projects; it writes papers in LaTeX--standard in academic math--and this website makes it easy to write papers and share with others in your group.
    Grading and Project Deadlines Your grade will be based on:
  • Research proposal: 10%, due October 6. Who is in your group, what are you modelling, what data will you use, list three questions you want to investigate; motivate and clearly write this up in a formal report.
  • Progress report: 10%, due October 27: you should have a formal writeup of (1) your introductory section (non-technical), (2) precise framework of your problem, (3) explain where your data comes from, (4) partial results, (5) any obstacles you have encountered, (6) your plan for the rest of the project. You should have partial results to present to the class.
  • Presentations to the class: 10%, during part of class time, from mid October onward; each member of your group must present some material. Presentations will be based on the progress report; time permitting, some groups may be able to give a short, earlier presentation based on the proposal.
  • Final written project: 50%, due November 22; (nine days before the course ends).
  • Homework on new material: 20%, assigned throughout the course.
    • As in previous years, the grading and grade distribution will be reminiscent of an Arts course; historically the average has been in the low 70's, and top marks are only given for projects with clear and interesting writeups of difficult research. Historically projects usually obtain good results, but only occasionally have a stellar writeup.
    Research Projects Research projects can be done in groups of 3 students; depending on enrolment, there will be some flexibility in group sizes.
    Projects generally model something in the real world and involving linear programming (e.g., simplex method for solving LP's, branch and cut method for solving integer LP's, etc.). Most projects involve some data, real or (partially) synthetic; finding the real data or generating realistic synthetic data can be a significant part of the problem.
    For project ideas, you can look at Prof. Anstee's Math 441 course last year. I will also provide some other project ideas and give interesting questions to ask in the latter part of September. Please tell me your project idea before you present your proposal; you are encouraged to consult me during the term whenever you have questions or difficulties arise.
    Tell Me Something We Don't Already Know Ideal research projects should tell me something that we don't already know.
    For example, if you are working with data that tries to schedule UBC exams to minimize the number of exam conflicts (or hardships), here are some things I know:
  • The longer the alloted exam period, the fewer the number of conflicts and hardships in an optimal schedule.
  • If the number of exam time slots times the number of chairs in the univeristy is less than the sum of the number of students in each course, there will be at least one conflict.

    • Here are some things I don't know:
  • Fix a set of classes, of students, and of class lists (of which students are taking which classes). As the alloted exam period shrinks, does the number of conflicts increase gradually, or is there a sharp threshold? (I'm guessing that there is a pretty sharp threshold.)
  • Say that UBC takes certain large classes with many sections, and requires each section to have its own exam; now different sections of the same class can be scheduled at different times. Does this policy change significantly affect the number of exam conflicts?

    • Can you draw some useful principles based on your results?
    New Material Topics to be covered (tentatively):
  • September:
    • Roughly 1 week: Review Math 340: LP's (linear programs) as models, the simplex method, matrix notation for LP's and dictionaries, revised simplex formulas, dual LPs, dual dictionaries, sensitivity analysis. (Chapters 1-6, 8, 10 of Chvatal).
    • Roughly .5 weeks: Linear programming without linear programming: the mere existence of the simplex method tells us some very important facts regarding matrix games, L-1 curve fitting, L-infinity (or Chebyshev) curve fitting, bipartite matching, etc.
    • Roughly 2 weeks: Ideas for Projects: Modelling with LP's and ILP's (integer LP's), more applications, data and synthetic data, research project ideas (some general ideas, some detailed).
  • October and November (there will also be presentations during part of this time), topics from (tentative list):
    • more applications; ILP's (integer LP's) and "branch and bound"; non-bipartite matching; nonlinear convex optimization; LP's and lower bounds for randomized algorithms; other appearances of LP's in theoretical computer science.

    • UBC Math Home| Joel Friedman Home| Course Materials