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 I recommend Gurobi for projects and homework. My last Math 340 homepage (Fall 2015) appears here; I will refer to it when reviewing Math 340 material.
Boards Scans, Etc. Scan of boards for: 09_11, 09_13, 09_15, 09_18,
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.
  • 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).
    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.
  • Homework Late homework will not be accepted. Your two lowest scores will be dropped in the overall homework computation.
    Homework #1: TBA.

    UBC Math Home| Joel Friedman Home| Course Materials