MATH 441 Homepage, Fall 2017
This page concerns MATH 441--Math Modeling: Discrete Optimization
This page has the most up-to-date information on the course(s) and
supersedes any other document.
Here is a
guide to the grading of presentations,
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
The progress report should be roughly 3-5 pages (i.e. 600-1000 words).
sample progress report and its
LaTeX source (which I have given a .txt
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
slides for a sample proposal
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.
We will discuss the Markowitz model and non-linear programming: see
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),
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.
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:
(from this point onward,
missing scans indicates no new material and no
written class notes)
11_06 class based on this,
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.
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
Math 441 course last year, and will borrow ideas from
Math 444 course last year;
both these webpages have some good resources.
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
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).
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.
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.
(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).
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
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
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.
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
Historically projects usually obtain good results,
but only occasionally have a
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
Math 441 course last year. I will also provide some other project
ideas and give interesting questions to ask in the latter part of
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
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
Can you draw some useful principles based on your results?
Topics to be covered (tentatively):
October and November (there will also be presentations during part
of this time), topics from (tentative list):
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,
more applications; ILP's (integer LP's) and "branch and bound";
nonlinear convex optimization;
LP's and lower bounds for randomized algorithms;
other appearances of LP's in theoretical computer science.