
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 
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 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.

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).

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.

Homework 
Late homework will not be accepted. Your two lowest scores will be
dropped in the overall homework computation.
Homework #1: TBA.

