
MATH 441 Homepage, Fall 2017
This page concerns MATH 441Math Modeling: Discrete Optimization
ProblemsSection 101.
This page has the most uptodate 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 37 pages (i.e., 6001400 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 35 pages (i.e. 6001000 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 talkeither about the proposal or
(later in November) about the researchand be prepared to answer
questions on the talk; see grading scheme below.

Markowitz Model 
We will discuss the Markowitz model and nonlinear 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 (Nonlinear) Programming.
We will also refer to part of Chapter 24 of
"Linear Programming" by Vanderbei, 4th edition.

Office Hours 
By appointment for nowemail 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 1115).
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
(standalone) 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 LaTeXstandard in academic mathand 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 (nontechnical), (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 16, 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, L1 curve fitting, Linfinity (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";
nonbipartite matching;
nonlinear convex optimization;
LP's and lower bounds for randomized algorithms;
other appearances of LP's in theoretical computer science.

