MATH 441 Homepage, Fall 2018
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. Some of the most basic course information on this website is replicated in this course overview (PDF).
| News |
Here is the
current class presentation
schedule, sorted by day.
The class presentation schedule was computed on 11_09 using this Python/Gurobi program based on this data (and the random number seed 1448). We will use this presentation grading rubric. Final reports are due Friday, November 30, 11:59pm, on Canvas. |
|---|---|
| Progress Reports |
Consult the
project requirements and guidelines for
requirements on the progress report; we will discuss
last year's sample progress report
during class; in October 26 we made
some annotations on this sample
report to remind you of the points below:
make sure that:
your overview (subsection 1.1) has at most 50 words,
your optional motivation (subsection 1.2) has at most 30 words,
and your specific problems (subsection 1.3) has at most 140 words,
and all of Section 1 makes clear and focuses on
what type of LP/IP/QP model you will
use.
All models in Section 2 must clearly identify: the decision variables
and their interpretation, the objective function, and constraints,
and the parameter(s) (or other variation) in your LP/IP/QP.
Your project must focus on an LP/IP/QP and the parameter(s); you must compare the optimal solutions of least five different LP/IP/QP problems in your final report. You must submit the LaTeX source code (here is the source for last years' example) along with the PDF version of your progress report. Consult the project requirements and guidelines for more information. |
| Older News |
|
| Overview |
This course involves applications of linear programming and related
optimization such as quadratic programming and integer programming;
you are assumed to have seen linear programming.
The focus of the course is a research project.
For B.A. students, this course counts as a
"research intensive approved course."
Your grade is computed as follows: research proposal, due Sept 28 (5%); progress report, due Oct 22 (10%); class presentation, during November (5%); final project, due Nov 21 (65%); homework on class material, assigned throughout the course (15%). (There are no exams.) 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. Some of the most basic course information on this website is replicated in this course overview (PDF). |
| Projects |
Most of your grade is based on a project, to be done in groups of 3-4
students; depending on enrolment and demand, smaller groups may be
possible.
All reports must be submitted in LaTeX;
overleaf.com lets
you share projects, written in LaTeX.
Here are the
project requirements and guidelines;
these
applications of LP's and ILP's
are possible project topics.
We will spend the first few weeks discussing applications suitable for Math 441 projects; here is a list of some applications discussed in class. |
| Textbooks and Resources |
All required textbooks and resources are available for free to anyone with a
UBC CWL. They include:
Other resources include: |
| 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), appointments will be scheduled more rigidly. |
| Boards Scans, Etc. |
Scan of boards for:
09_05 to 09_07,
09_12 to 09_24
(Focused on Applications of LP and IP),
09_26 to 10_05
(Focused on TSP, Quadratic Programming, Project Ideas),
10_10 to present.
On 10_22 and 10_24, we discussed some aspects of Python and Gurobi based on class.22.Oct.2018.txt and (the Python versions of) these examples on the Gurobi website. Starting 10_26, we covered the following programs and data: Easy_Reader directory: 1README.txt, data5x4.txt, simple_reader.txt, polite_reader.txt, polite_reader.py. On 10_29 we began discussing some aspects of Python and Gurobi based on class.29.Oct.2018.txt and these files: Easy_Gurobi_Models directory: 1README.txt, fibonacci_warm_up.txt, TV4.lp (from September), examine_TV4.txt, simple_coffee.txt. The mip1.py (mixed integer program), qp.py (quadratic program) under the "Build a Simple Model" heading of the Gurobi examples page (we looked at the python versions); also sudoku.py under the "A Few Applications" heading. Pres_Scheduler directory: 1README.txt, pres_sched_4toyObj.txt, data5x4.txt, data8x4_same.txt, data8x4_vary.txt, presentation_sched.txt, presentation_sched.py, quiet_scheduler.py. On 10_31 we corrected some minor problems in the current Wikipedia page on the TSP (Traveling Salesman/Salesperson Problem), and discussed a simple TSP formulation with no objective function (i.e., which produces some feasible solution), an improved version, and two further improvements (with random distances between cities): jf_tsp_ana1.py and jf_tsp_ana2.py (which we produced using Spyder (running Python 2.7) in the Anaconda navigator). On 11_02 we worked on these questions about the program worksheet.py; this worksheet uses one of the data files of our presentation scheduler, such as data8x4_same.txt or data8x4_vary.txt. On 11_05 we worked on this start to a Latin square solver (largely based on sudoku.py supplied by Gurobi). Notes starting 11_07 (branch and bound, branch and cut). On 11_16 we discussed the bin packing problem solvers: min_packingNoWrite.py and min_packingWithWrite.py (the second program is the same as the first, except at the end of the program we write the results to an output file); both of these python/Gurobi programs read data files with some lines that are CSV's (comma separated values), and some that are comments (that start with a # followed by a space), such as pack5.txt, pack10.txt, pack25.txt, pack30.txt. Although Gurobi had no problem solving these exactly, it wasn't able to exactly solve pack35.txt and packRelPr25.txt (the file packRelPr25.txt was generated using the script create_prob.py and the data file relPrime25.txt. Notes from 11_21 focus on the suggested format of the final report. On 11_23 we suggested that part of your project group may write *.lp files for toy examples and small models if they had trouble debugging their use of Gurobi Model class and/or Python. On 09_21 we solved the first of these Sudoku problems (which I got from http://www.mathsphere.co.uk/downloads/sudoku/10201-easy.pdf). On 10_03 we made remarks and annotations, mainly on the TSP (Traveling Salesman/Salesperson Problem), resulting in this PDF file based on this MIT Open Courseware, MIT15-053S13, Lect 14. |
| Software |
We will use Gurobi in class examples; it offers
free licenses for univesity students and is competitive with
the best commercial products (e.g., CPLEX and Mosek); see
this year's class Gurobi homepage The examples we give in class will run the "Gurobi shell" in a terminal window (this is what happens if you run the Gurobi app); this is just the Python shell with some add-ons. There are more examples (with older links) in last year's class Gurobi homepage. I recommend you use Gurobi for the homework and your projects; some homework may require another language, such as Maple or R; you may use other software, but you need to make sure that your software works and can do what is required in the homework (e.g., solve linear programs and integer linear programs of moderate size, generate sequences of random numbers and plot data points). |
| Prerequisite |
The prerequisite for the course is Math 340.
In class 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. |
| Homework |
Late homework will not be accepted. Your two lowest scores will be
dropped in the overall homework computation.
Homework 1 is due on Sunday, September 23, 11:59pm at canvas.ubc.ca. Homework 1 solutions and Gurobi lp file for the LP on Problem 1, output from Gurobi, Gurobi lp file for the IP, output from Gurobi. Homework 2 is due on Wednesday, October 3, 11:59pm at canvas.ubc.ca. Homework 2 solutions and Gurobi lp file for the LP on Problem 1, output from Gurobi. Homework 3 is due on Wednesday, October 24, 11:59pm at canvas.ubc.ca. Homework 3 solutions. Homework 4 is due on Monday, November 12, 11:59pm at canvas.ubc.ca. Sample solution (in Python/Gurobi) for Homework 4 and sample output. Homework 5 is due on Wednesday, November 21, 11:59pm at canvas.ubc.ca. Sample solution (in Python/Gurobi) for Homework 5 and sample output (plus some text that explains why the solutions are different). Homework 5 is the last homework. |
| New Material |
New material includes a discussing of optimization related to linear
programming such as integer programming (and "branch and bound"),
convex programming, and quadratic programming.
We will cover applications such as:
when linear programming can handle non-linear optimization
(e.g., progressive taxation);
scheduling class presentations;
time restricted task scheduling;
bin packing and related problems (using integer linear programming);
the Markovitz model (using quadratic programming);
L-1 and L-infinity (Chebyshev) curve fitting; matching.
We will also discuss some principles of linear programming that you may have seen in Math 340, especially those related to modeling; the most important is that the simplex method guarantees that there are optimal solutions to LP's that have many zero-valued decision variables if you have many more decision variables than constraints. We will also briefly discuss common mistakes in scientific writing. |
| UBC Math Home | | | Joel Friedman Home | | | Course Materials |