MATH 441 (2019W)

Formulation of real-world optimization problems using techniques such as linear programming, network flows, integer programming, dynamic programming. Solution by appropriate software.

This course is eligible for Credit/D/Fail grading. To determine whether you can take this course for Credit/D/Fail grading, visit the Credit/D/Fail website. You must register in the course before you can select the Credit/D/Fail grading option.
Credits: 3

Pre-reqs: MATH 340.

Instructor:
Jozsef Solymosi
email: solymosi@math.ubc.ca
office: MATH Building 220  

In this course you will work in teams of 4-5(-6) students. (Note: 6 is not allowed when you start a group) Most of your grade is based on a project, to be done in groups. Students not in a self-selected group will be assigned randomly into new groups.


HW 1 (Due Sept 26, Thursday, in class or by email before class)
HW 2 (Due Oct 10, Thursday, in class or by email in a single PDF file before class)
HW 3 (Due Oct 24, Thursday, in class or by email in a single PDF file < 1MB. Before class, or points will be deducted!)
HW 4 (Due Nov 12, Tuesday, in class or by email in a single PDF file < 1MB. Before class, or points will be deducted!)

Grading:
- HW assignments 20%.
- Team work evaluation (Presentation, essay (written summary of your project), and individual Q/A during presentation) 80%.

Schedule
First presentations:
Oct 8: Team1, Team 2
Oct 10: Team 3, Team 4
Oct 15: Team 5, Team 6
Oct 17: Team 7, Team 8
Oct 22: Team 9, Team 10

In the first presentation (20 minutes + 10 minutes for questions) you
- introduce the selected NP complete problem
- prove (if complicated then sketch the proof) that it is NP-complete
- explain how you are planning to solve the problem
- other remarks (polynomial approximation, relaxation, other variants, etc.)

The due date of your essay is Nov 15.

Second presentations (based on the instructions after the first presentation):
Nov 12: Team 10, Team 9
Nov 14: Team 8, Team 7
Nov 19: Team 6, Team 5
Nov 21: Team 4, Team 3
Nov 26: Team 2, Team 1

After a random permutation the teams are

1 Knapsack
2 How weather, traffic ...
3 Battleships
4 Sudoku
5 Hamiltonian path
6 Graph colouring
7 Assembling Bitcoin
8 Traveling salesman
9 Hashiwokakero
10 Kuromasu

In the exceptional case, if you are unhappy your team's performance, and you think it does not reflect your knowledge of the subject, then you can choose to write a final exam.

In this case, the previous 20%+80%  (HW included) will count as your term work with weight 50%. Your final counts for 50%. This decision should be made at least 2 weeks before the end of the term, Nov. 15, and submitted to me in writing.


You will learn the basics of combinatorial optimization.

Then, you (your team) will choose an NP-complete problem.

NP-complete problems (List from Wikipedia)

You will present the selected problem and will try to come up with a solution plan.

You are expected to use an optimization software in order to find the solution of a given problem.

List of optimization software (List from Wikipedia)

I don't expect prior knowledge of programming, however it is not a bad thing if one of the team members has some affinity to coding.

There will be regular homework assignments. Late homework will not be accepted. Your lowest score will be dropped in the overall homework computation.

Office hours are by appointment  -- email me and let me know when you are free over the next few days.

Each member of your group must present some material/slides, and must be prepared to answer questions on this material. Your group needs to email a PDF file of your slides by 7am on the day of your presentation (it's OK to make small corrections to the slides and to send me a revised set of slides later in the day, after your talk).

Suggested readings:

The Golden Ticket
P, NP, and the Search for the Impossible  (UBC Library link)

Millennium Problems (How to earn one million dollars?)

P, NP, and NP-Completeness: The Basics of Complexity Theory (This is a graduate level treatment of complexity theory) (UBC Library link)


Topics covered in class.
Polynomial reductions
Polynomial approximation
Optimization problems mentioned in class

Academic Misconduct:

1. UBC takes cheating incidents very seriously. After due investigation, students found guilty of cheating on tests and examinations are usually given a final grade of 0 in the course and suspended from UBC for one year.
2. While students are encouraged to study together, they should be aware that blatant copying of another student's work is a serious breach of academic integrity. Please discuss with your instructors their expectations for acceptable collaboration on any assigned coursework. Cases of suspected cheating will be investigated thoroughly.
3. Note that academic misconduct includes misrepresenting a medical excuse or other personal situation for the purposes of postponing an examination or quiz or otherwise obtaining an academic concession.

Statement on UBC's Policies and Resources to Support Student Success:

UBC provides resources to support student learning and to maintain healthy lifestyles but
recognizes that sometimes crises arise and so there are additional resources to access including those for survivors of sexual violence. UBC values respect for the person and ideas of all members of the academic community. Harassment and discrimination are not tolerated nor
is suppression of academic freedom. UBC provides appropriate accommodation for students
with disabilities and for religious and cultural observances. UBC values academic honesty
and students are expected to acknowledge the ideas generated by others and to uphold the
highest academic standards in all of their actions. Details of the policies and how to access
support are available at
https://senate.ubc.ca/policies-resources-support-student-success